P2126 Male Servants in Mzc's Household

The thing between mzc and djn is not yet widely known, so we are going to spread the word.

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.

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.

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

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