L. The Shortest Path
time limit per test
3.0 с
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a directed weighted graph with N nodes and M edges. Your task is to find the minimum shortest path between any pair of nodes in the graph. As the weight of the edges can be negative, the path is allowed to visit the same node multiple times.

Formally, let F(u, v) be the shortest path between the two nodes u and v, find the minimum F(u, v) over all pairs (u, v) (1 ≤ u, v ≤ N) (u ≠ v). If there is no path between a pair of nodes u and v, then F(u, v) = ∞.

Input

The first line of input contains a single integer T (1 ≤ T ≤ 100), the number of test cases.

The first line of each test case contains two integers N and M (2 ≤ N ≤ 2000) (1 ≤ M ≤ 5000), where N is the number of nodes in the graph, and M is the number of edges.

Each of the following M lines contains three integers U, V and C (1 ≤ U, V ≤ N) (U ≠ V) ( - 106 ≤ C ≤ 106), representing that there is an edge from node U to node V with cost C.

Note that the graph may contain multiple edges between the same pair of nodes in the same direction.

Output

For each test case, print the minimum length of a shortest path in the graph, or "-inf" if the length of the shortest path is negative infinity.

Example
Input
3
3 3
1 2 -1
2 3 -3
3 1 -5
4 5
1 3 0
1 2 -2
2 3 3
3 4 1
4 1 -1
4 4
1 2 5
2 3 -3
3 4 -3
1 4 2
Output
-inf
-3
-6