Description

mzc is very rich (just kidding). He has $n$ male servants. Now mzc wants to gather them all together (for reasons unknown). Given the communication times between mzc and the male servants, please compute the total time needed to call each of them (counting repeated uses). It is guaranteed that everyone can be called.

Input Format

The first line contains a number $n$, indicating there are $n$ male servants.
The second line contains a number $m$, indicating there are $m$ communication routes.
Then follow $m$ lines, each with three numbers $a_i, b_i, c_i$, meaning that the time needed for communication between the $a_i$-th male servant (or mzc) and the $b_i$-th male servant (or mzc) is $c_i$ (bidirectional). Here, $a_i$ or $b_i = 0$ denotes mzc.

Output Format

One line with a single number $sum$, representing the total time required to call each of them.

5
12
0 2 15
2 3 20
3 5 13
1 3 29
0 1 30
2 4 21
0 3 23
5 1 48
0 4 17
0 5 27
1 2 43
2 5 41

94

Hint

Constraints: $1\le n\leq2300$, $1\le m\leq4\times10^5$.

Translated by ChatGPT 5