Alice found a new kingdom known as Wonderland. Wonderland consists of N villages numbered from 1 to N and M uni-directional roads between some villages. Each of these road is associated with an integer value, say X. If a person travels through a road with value X, her total wealth increases by X (where X can be both positive and negative). Alice was quick to realize that if she travels through the roads optimally she can earn a lot of money.
Alice is currently on village 1 with no money (her initial wealth is 0) and Wonderland's exit is on village N. Alice wants to earn as much money as possible before leaving the kingdom but she knows being too greedy is not good, so she decided she will be satisfied once she becomes a quadrillionaire (quadrillion =1015).
You have to find whether Alice can become a quadrillionaire or not. If not, then you have to find the maximum wealth Alice can have when she leaves the kingdom.
Note:
Constraints
1≤N≤3000
1≤M≤5000
−109≤X≤109
Input format
The first line contains T (1≤T≤10), the number of testcases.
The first line of each testcase contains two integers N and M, the number of villages and the number of roads in Wonderland respectively.
Each of the following M lines contain 3 integers u v x, denoting there is a road from village u to village v with value x.
output format
For each testcase:
If Alice can become a quadrillionaire print "YES" else print "NO" and in a new line print the maximum wealth Alice can have when she leaves the kindgom.