I. Turism in Yekaterinbug
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Many may think: "What will I do in Yekaterinburg? This city is in the end of the world!!". However, many important things have happened in this city, so it has many monuments and historical places. To name a few, Yekaterinburg has a monument that is a huge computer keyboard located in the banks of river Izet; a monument to Michael Jackson (!!); in the Ipatiev mansion some Romanovs were murdered (czar Nicolau, his wife and children); also there was an anthrax leak in 1979; an american U2 pilot was captured and convicted for espionage; among others. Therefore, there is plenty to do in the city.

Yekaterinburg's tourism central built a map with all the main tourist attractions in the city, as well as beautiful excursions connecting these attractions. This map also shows a difficulty level for each excursion (taking in account duration, paving of the streets, etc.) and the direction in which it should be traversed.

They wish to build a route that goes through all the tourist attractions and excursions. A contest was made to create this route, and also to honor one of the sister cities of Yekaterinburg: Kaliningrad, that was named Königsberg until the end of the second world war. The idea was to build a route that started in one of the attractions, and going through all excursions returned to the starting point.

We know that, as in the case of the bridges of Königsberg, it isn't always possible to build such route. That's why the central allowed excursions to be traversed more than once, if necessary. However, the central required that the total difficulty of the route (the sum of the difficulties of each excursion in it, counting repetitions) was minimal.

Your task is to find this minimal total difficulty, or determine if there exists no such route.

Input

On the first line T, the number of test cases.

The first line of each test case has two integers N and M, the number of tourist attractions and the number of excursions, respectively. The i-th of the next M lines has three integers ai, bi and di, meaning the i-th excursion starts at ai, ends at bi and has difficulty di.

Limits

  • 1 ≤ T ≤ 100
  • 2 ≤ N ≤ 50
  • 0 ≤ M ≤ N2 + 103
  • 1 ≤ ai, bi ≤ N
  • ai ≠ bi
  • 1 ≤ di ≤ 3·104
  • The sum of N over all test cases won't exceed 1500.
Output

For each test case print the minimal total difficulty of the desired route. If there is no such route, print -1.

The answer may not fit in a 32-bit integer.

Example
Input
3
2 2
1 2 10000
2 1 30000
4 7
1 2 1
2 1 2
2 3 4
2 3 4
3 2 3
3 4 10
4 3 100
3 2
1 2 1000
2 3 1000
Output
40000
127
-1