Problem 1127 --Longest path1127: Longest path
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 1317 Solved: 153
[Submit][Status][Web Board]Description
David has a graph of n nodes and m directed edges, and he wants to know the longest path in this graph. We promise that there is no loop in the graph.
Input
The first line will be an integer T, which is the number of the test cases(1 <= T <= 10). For each test case, the first line will be two integers n and m(1 <= n <= 100000, 1 <= m <= 200000). The following are m lines, and each line will be three integers x, y and z(1 <= z <= 300000), which means there is an directed edge weighted z from x to y.
Output
For each test, output the longest path in this graph.
Sample Input
1
3 4
1 2 5
2 3 4
1 3 10
1 3 20
Sample Output
20
HINT
Source
[Submit][Status]