1502. 荒野迷路

【题目描述】

一天，你和土豪开车到郊外游玩，但你们突然发现车子快没油了……

剩余的油量不够开到最近的加油站，因此必须有一个人拨打燃油救援电话，并且负担拖车费和油费。

但你们都不愿意掏这笔钱，因此你和土豪商定：一直开下去，每到路口都换人驾驶，车子没油时的驾驶者掏钱。特别地，如果开到路口后刚好没油，仍然换人（例如，若你将车开到路口后刚好没油，则土豪掏钱）。

假设你们现在在1号节点，你先驾驶，油箱里有K升油。现在给出N个路口和它们之间的M条道路，你是否一定获胜（即让土豪掏钱）？

【输入格式】

输入包含多组数据。

输入文件的第一行是一个整数T(1<=T<=10)，代表数据组数。

对每组数据，第1行是3个整数：K,N,M。

接下来的M行，每行是三个正数a,b,w，表示路口a,b间有一条道路，走这条道路需要耗费w升油（道路是双向的）。路口用1,2,…,N编号。

【输出格式】

对每组数据，若你一定能获胜，输出一行“Yes!”，否则输出一行“No!”

【样例输入】

3

5 2 1

1 2 5

5 2 1

1 2 6

6 3 3

1 2 5

1 3 2

2 3 3

【样例输出】

Yes!

No!

Yes!

【提示】

样例包含3组数据。

第1组数据描述了一个含2个点的图，1和2之间有一条权值为5的边。你们在点1，油箱中有5升油。显然你可以把车子开到2，从而获胜。

第2组数据与第1组数据类似，但1和2之间的边权值为6，所以你无法将车子开到点2，你无法获胜。

第3组数据描述了一个含3个点的图。如果你把车开到点3，那么土豪下一步可以把车开到点2，之后油箱中剩余1升油，你无法继续驾驶，此时土豪获胜。但你可以先把车开到点2，之后油箱中剩余1升油，土豪无法继续驾驶，你获胜。因此你一定能获胜。

对于30%的数据，1<=N<=20，1<=M<=100，1<=K<=100.

对于100%的数据，1<=N<=500，1<=M<=1000，1<=K<=5000，1<= w<=100.

（由于你们拙劣的驾驶技术）你们只可能在这N个路口和M条道路上开车。