In order to strengthen the communication between the island, the government wants to build bridges between some islands. Now, the government gives you the cost money between each island, can you find the way to build bridges to link all islands but cost the minimum money.

Input until EOF.

First line will give you two integers N (4 <= N <= 100)(the id of islands are from 1 to N) and M (N - 1 <= M <= N * (N - 1) / 2), N means the number of islands, M means the number of bridges can be built.

Next M lines, each line contains three integers x, y, and c (0 < c < 100), means there exists the cost money c between x and y.

For data.in, there will not exist two bridges between two islands, and all islands will be linked by bridges.

Print the minimum cost money to link all islands.