11271127 SUSTech Online Judge
Problem 1127 --Longest path

1127: 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]