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

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

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

```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.

Shell