Xiao Ming, who is involved in archaeology, has obtained a treasure map. The map marks $n$ treasure houses buried underground and provides $m$ roads that can be developed between these $n$ treasure houses, along with their lengths.

Xiao Ming is determined to visit the treasure houses in person to retrieve the treasures. However, each treasure house is very far from the surface, which means it is very difficult to build a road from the surface to a single treasure house, while developing roads between treasure houses is relatively much easier.

Moved by Xiao Ming's determination, an archaeological sponsor has decided to sponsor him for free to build one passage from the surface to a treasure house of his choice.

On this basis, Xiao Ming also needs to consider how to excavate roads between the treasure houses. Roads that have already been excavated can be traversed freely at no cost. When a new road is excavated, Xiao Ming will go out with the archaeological team to reach the treasure house at the end of that road. Additionally, Xiao Ming does not want to develop redundant roads, meaning that roads between two treasure houses that have already been connected do not need to be developed again.

The cost of developing a road is: The length of this road $\times$ the number of treasure houses passed through from the treasure house sponsored by the sponsor to the starting point of this road (including the treasure house sponsored by the sponsor and the starting point of this road).

Please write a program to help Xiao Ming select the treasure house to be sponsored and the subsequent roads to be excavated, such that the total cost of the project is minimized, and output this minimum value.

Input

The input file is named treasure.in. The first line contains two space-separated integers $n$ and $m$, representing the number of treasure houses and the number of roads. The next $m$ lines each contain three space-separated integers, representing the two treasure house IDs connected by a road (IDs are $1 \sim n$) and the length $v$ of this road.

Output

The output file is named treasure.out. Output a single line containing one integer, representing the minimum total cost for Xiao Ming.

Examples

Input 1

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

Output 1

4

Note 1

Xiao Ming chose to have the sponsor connect to treasure house 1. Xiao Ming developed road $1 \to 2$, excavating treasure house 2. He developed road $1 \to 4$, excavating treasure house 4. He also developed road $4 \to 3$, excavating treasure house 3. The total project cost is: $1 \times 1 + 1 \times 1 + 1 \times 2 = 4$ $(1 \to 2) \quad (1 \to 4) \quad (4 \to 3)$

Input 2

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

Output 2

5

Note 2

Xiao Ming chose to have the sponsor connect to treasure house 1. Xiao Ming developed road $1 \to 2$, excavating treasure house 2. He developed road $1 \to 3$, excavating treasure house 3. He also developed road $1 \to 4$, excavating treasure house 4. The total project cost is: $1 \times 1 + 3 \times 1 + 1 \times 1 = 5$ $(1 \to 2) \quad (1 \to 3) \quad (1 \to 4)$

Input 3

(See treasure/treasure3.in)

Output 3

(See treasure/treasure3.out)

Constraints

For 20% of the data: Guaranteed that the input is a tree, $1 \le n \le 8$, $v \le 5000$, and all $v$ are equal.

For 40% of the data: $1 \le n \le 8$, $0 \le m \le 1000$, $v \le 5000$, and all $v$ are equal.

For 70% of the data: $1 \le n \le 8$, $0 \le m \le 1000$, $v \le 5000$.

For 100% of the data: $1 \le n \le 12$, $0 \le m \le 1000$, $v \le 500000$.