Surge is hosting a Christmas party at his house and needs to stock up on juice!

Surge's town consists of ~N~ houses and ~M~ two-way roads connecting them. Surge lives in house ~1~. Each road ~i~ takes ~w_i~ minutes to walk across. He wants a person from every house in his neighbourhood to bring a bottle of juice to his house. What is the minimum total time that the citizens can spend walking from their house to Surge's house?

Constraints

In all test cases, ~1 \le w_i \le 2 \times 10^5~ for all ~1 \le i \le M~

Subtask 1 [50%]

~1 \le N \le 1000~, ~1 \le M \le 3000~

Subtask 2 [50%]

~1 \le N \le 10^5~, ~1 \le M \le 2 \times 10^5~

Input Specification

First line: ~N~ (the number of houses) and ~M~ (the number of roads).

The next ~M~ lines each contain ~u_i~, ~v_i~, and ~w_i~ indicating a two-way road connecting houses ~u_i~ and ~v_i~ and takes ~w_i~ minutes to traverse (~1 \le u_i, v_i \le N~).

Output Specification

One integer: the minimum total time possible in minutes.

Sample Input 1

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

Output for Sample Case 1

36

Explanation for Sample Case 1

The town looks as such:

• House ~5~ can go straight to house ~1~, taking ~3~ minutes.
• House ~3~ can go to house ~5~ then house ~1~ taking ~13~ minutes.
• House ~2~ can go to house ~5~ then house ~1~ taking ~9~ minutes.
• House ~4~ can go to house ~5~ then house ~1~ taking ~11~ minutes.

The total time taken was ~3+13+9+11=36~ minutes.