A company has n offices numbered 1 to n and a list of m possible cables. Cable i would connect offices u and v at a cost of w. Cables may repeat, and a cable may join an office to itself (it is never useful). Choose some cables so that every office can reach every other office through the chosen cables, with the smallest possible total cost.
The first line has n and m. Each of the next m lines has u, v and w.
Print the minimum total cost, or -1 if it is impossible to connect all offices.
1 <= n <= 100000 0 <= m <= 200000 1 <= w <= 10^9 The answer can exceed 32 bits.
1000 ms256 MB
4 5 1 2 1 2 3 4 3 4 2 1 3 3 1 4 10
6
Take 1-2 (1), 3-4 (2) and 1-3 (3): total 6.
3 1 1 2 4
-1
Office 3 cannot be connected.
