Problem Description

There are $ N $ houses and $ M $ roads in the city where Takahashi lives. The houses are numbered from $ 1 $ to $ N $. Takahashi lives in house $ 1 $. The roads are also numbered from $ 1 $ to $ M $. The $ i $-th road connects house $ u_i $ and house $ v_i $ bidirectionally with a length of $ l_i $ meters.

Takahashi is looking for the "Blue Bird of Happiness" who is said to be in one of the houses in the city. In fact, the "Blue Bird of Happiness" is in Takahashi's house, and Takahashi knows this. However, he thinks it would be less interesting without at least a semblance of a search journey, so he reluctantly decides to plan a trip.

Takahashi plans to start from his house, visit several houses without passing the same road more than once, and return to his house at the end. To create excitement, he plans to visit at least one house other than his own during the trip. Takahashi wants to end this charade as soon as possible, so he thinks the best plan is the one with the smallest total length of the roads traveled.

Given the information about the houses and roads in the city where Takahashi lives, determine whether Takahashi can plan an optimal trip under the above conditions. If it is possible to plan an optimal trip, find the total length of the roads traveled.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ u_1 $ $ v_1 $ $ l_1 $ $ u_2 $ $ v_2 $ $ l_2 $ : $ u_M $ $ v_M $ $ l_M $

• The first line contains the number of houses $N(3\ ≦\ N\ ≦\ 300)$ and the number of roads $M(3\ ≦\ M\ ≦\ N(N-1)/2)$ separated by a space.
• The next $ M $ lines contain the house numbers $u_i,\ v_i(1\ ≦\ u_i\ ＜\ v_i\ ≦\ N)$ connected by the $ i $-th road and the length of that road $l_i(1\ ≦\ l_i\ ≦\ 10^5)$ separated by a space.
• If $i\ ≠\ j$, then at least one of $u_i\ ≠\ u_j$ or $v_i\ ≠\ v_j$ holds.

Output Format

If it is not possible to plan an optimal trip, output $ -1 $. If it is possible, output the total length of the roads traveled in one line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

5 7
1 2 2
1 4 1
2 3 7
1 5 12
3 5 2
2 5 3
3 4 5

Sample Output #1

13

Sample Input #2

5 4
1 2 1
1 3 1
1 4 1
1 5 1

Sample Output #2

-1

Sample Input #3

10 12
1 4 3
1 9 1
2 5 4
2 6 1
3 7 5
3 10 9
4 7 2
5 6 6
5 8 5
6 8 3
7 9 5
8 10 8

Sample Output #3

11

Notes/Hints

Sample Explanation 1

The houses and roads look like this:  The optimal plan is to visit the houses in the order $1,\ 2,\ 5,\ 3,\ 4,\ 1$. The plan to visit the houses in the order $1,\ 2,\ 1$ does not satisfy the condition as it passes the first road twice.

Sample Explanation 2

It is not possible to plan a trip without passing the same road more than once. Therefore, output $ -1 $.

见题面 Input 部分

见题面 Output 部分