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]