Minimum Spanning Tree

Interview

Time limit1sMemory limit128 MB

Summary

Compute the total edge weight of a minimum spanning tree for a weighted undirected graph with up to 10,000 vertices and 100,000 edges, allowing negative weights.

Level: Medium4 of 10
Topics: Minimum spanning tree, Union-find, Greedy
Solved: No attempts yet

Problem

You are given an undirected weighted graph. Among all subgraphs that connect every vertex, find a tree whose total edge weight is as small as possible.

Such a tree is called a minimum spanning tree.

Input

The first line contains the number of vertices V and the number of edges E.

1 <= V <= 10,000
1 <= E <= 100,000

Each of the next E lines contains three integers A, B, and C, describing one edge. It means that vertex A and vertex B are connected by an edge with weight C.

Vertices are numbered from 1 to V.
C may be negative, and |C| <= 1,000,000.
There is always a path between any two vertices.
The total weight of the minimum spanning tree is within the range of a signed 32-bit integer.

Output

Print the total weight of the minimum spanning tree on one line.

Examples1

Example 1
Input
```
3 3
1 2 1
2 3 2
1 3 3
```
Expected output
```
3
```