Tianjin University Online Judge
Contests Virtual Contests Problems Submit Runs Status Rank List Forum

3518.   Buy Car
Time Limit: 1.0 Seconds   Memory Limit: 65536K
Total Runs: 626   Accepted Runs: 247



Brent hasn’t go out for a long time, so he is eager to go travelling. There are many cities he wants to visit, and he decides to visit all of them. What’ s more, he wants to go travelling by his car, but he has no car yet. Brent loves BMW car very much, so he wants to buy a BMW car. Now, Brent comes to a BMW 4S store, seeing many beautiful cars there. Well, different cars may have different fuel tank capacity, which means the distance the car can drive, so not every car can satisfy his needs. Thus, Brent hesitates to buy which one.
Given the cities Brent wants to visit and the distance between them. Brent only can refuel the car in the city. Can you help Brent to calculate the minimum fuel tank capacity of the car to satisfy his need?
You can assume that 1 liter gasoline can drive 10 kilometer and the fuel tank capacity is always an integer.

Input

The input contains multiple cases. The first line will consist of a single positive integer T (0 < T ≤ 20), which is the number of cases.
The first line of each case is two integers N(3 <= N <= 200),  M (0 <= M <= N * (N – 1) / 2), indicating the number of cities and the number of roads.
Then M lines follow. Each line contain three integers Ai, Bi and Ci (1 ≤ Ai, Bi ≤ N, 1 ≤ Ci ≤ 1000), indicating that there is a road between city Ai and city Bi, whose length is Ci  kilometer.
Please note all the cities are numbered from 1 to N.  Brent can visit one city more than once. And before the trip, Brent is in city 1.
The roads are undirected, that is, if there is a road between A and B, you can travel from A to B or from B to A.
There is at most one road between any two cities.

Output

Output one line for each test case, each line contains one integer indicating the minimum fuel tank capacity of the car. If there is no solution, please output -1.

Sample Input

3
3 2
1 2 10
2 3 40
3 3
1 2 10
2 3 40
3 1 25
3 1
1 2 10

Sample Output

4
3
-1



Source: TJU Team Selection Contest 2010 (3)
Submit   List    Runs   Forum   Statistics

Tianjin University Online Judge v1.3.0
Maintance:Fxz. Developer: SuperHacker, G.D.Retop, Fxz