Given a connected, undirected graph, a spanning tree of that graph is a subgraph which is a tree and connects all the vertices together. On a weighted graph, the weight of a spanning tree is the sum of the weights of its edges. A minimum spanning tree is a spanning tree with weight less than or equal to the weight of every other spanning tree.

Input

Input consists of different weighted, connected, undirected graphs. For each graph, the following integers are given: First, n ≥ 1 represents the number of vertices on the graph. Then, m represents the number of edges on the graph. Finally, a set of m weighted edges u,v,w is given by specifying its two end points u and v and its weight w ≥ 1. Vertices are numbered starting from 1. There are no edges connecting a vertex to itself, but there may be more than two edges connecting the same pair of vertices. Every given graph is connected. All weights are strictly positive integers.

Output

For every graph in the input, write the weight of its minimum spanning tree.

Public test cases

**Input**

5 6 1 2 3 1 3 8 2 4 5 3 4 2 3 5 4 4 5 6 3 3 2 1 20 3 1 20 2 3 100

**Output**

14 40

Information

- Author
- Jordi Petit
- Language
- English
- Official solutions
- C++ Python
- User solutions
- C++ Python