## 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