Minimum Cascading Spanning Tree

In the following definitions we suppose that G = (V, E) is an unempty undirected connected graph. V is the set of its vertices and E is the set of its edges. The task
We are given an undirected integer-weighted graph G = (V, E, φ), φ: E → ℤ. We have to find the weight of minimum cascading spanning tree of G. The weight of a tree is a sum of weights of all its edges.


The first line of input contains two positive integers N, M separated by space. N represents the order of the graph (number of vertices) and M represents the size of the graph (number of edges). Next, there are M lines of input, each line specifies completely one edge. We suppose that graph vertices are labeled 1, 2, 3, ..., N. The edge specification consists of three integer values separated by at least one space. First two values represent labels of the end vertices of the edge, third value represents its weight. Note that the edge weights might be negative. The edges and its end vertices are given in no specific order.
You may assume that the following relations hold: 2 ≤ N ≤ 500, N−1 ≤ M ≤ 10000. Absolute value of each edge weight does not exceed 109.


The output contains a single text line with integer representing the weight of minimum cascading spanning tree of the input graph.

Example 1

6 9
1 2 1
1 3 9
1 4 8
1 6 6
2 3 2
3 4 3
4 5 4
4 6 7
5 6 5
The input graph is depicted in the picture, the cascading center of the minimum cascading spanning tree (which is also depicted) is vertex 1. The picture also shows the decomposition of the set of vertices into corresponding equivalence classes.

Example 2

5 6
1 2 10
1 3 1
2 4 5
3 4 10
3 5 1
4 5 5

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout a stderr is available to him/her.

Public data