There are some cattle barns made of stakes and fences in Farmer John's (FJ) farm.
Two stakes are connected by only one fence, and each stake can be connected to all the other stakes with a fence.
A cattle barn is formed where the fence is closed.
The cows like to wander in their barns.
Due to the poor consideration, some cattle barns are so small that the cows there complain to FJ that it takes few steps back to the starting point. Therefore, FJ decides to tear down the cattle barn with the smallest circumference according to the public voices. Please find out this cattle barn.
Given M+1 lines, two integers N and M in the first line represent the number of stakes and fences. Let's number these N stakes as 1,2,3...N.
The following M lines each includes 3 integers A, B, L, indicating that there is a fence of which length is L connecting stake A and B. And there is definitely at least one cattle barn.
2<=N<= 100,1 <=M<=300, 1<=L<=1000.
Output 1 integer, representing the circumference of the smallest cattle circle.

Sample
Input:

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

Output:

11

Explanation:

Stake 1, 2, and 4 form the smallest cattle barn, of which the circumference is 11.

---

Special thanks: this is translated selflessly by LydiaCCC, who did not want to be named.