Description

Businessman is uesed to establishing trade-path between different cities in order to get a stable income£¨In this problem, a trade-path is a set of roads starting at a city and ending at the same city which should go through at least one other city.£©And the long-time cargo transportation is often accompanied by great risk.

Given a map of this region and the time from some city to another city, please help businessman find the trade-path which takes the least time.

Input

There are several test cases. The first line is the number of cases.

For each test case the first line contains two integer n,m, (1<=n<=100,0<=m<=10000) which denote the number of cities and road (directed road). The following m lines contains three integer ai,bi,di which means that It takes di time from the city ai to the city bi. (1<=ai,bi<=n,di<=1000000).

Output

For each case, print the time of the shortest trade-route at the beginning of a new line. If there is no legal trade-route in the map, print -1.

Sample Input

3
5 10
1 2 10
1 3 5
2 3 2
2 4 1
3 2 3
3 4 9
3 5 2
4 5 4
5 1 7
5 4 6
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50
4 5
1 2 10
1 3 20
3 4 10
2 4 5
1 4 50

Sample Output

5
65
-1

Hint

For the sample input 1, the solution is {2->3->2};

For the sample input 2, the solution is {1->2->4->1};

But for the sample input 3, there is no solution.

Author

Shell