Road to quadrillionaire

0

0 votes
Shortest Path Algorithms, Graph Theory
Problem

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:

  • It is always possible for Alice to reach village N.
  • Alice can take the same road multiple times.
  • Alice's final wealth when she leaves the kingdom can be negative.

Constraints

1N3000

1M5000

109X109

Input format

The first line contains T (1T10), 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.

Time Limit: 2
Memory Limit: 256
Source Limit:
Editor Image

?