Problem description

Has experienced more than 20 years of war, human beings finally defeated the worm, expelled them thoroughly, war ruins in the galaxies, galaxies governor according to an old saying goes "to get rich, first build roads", the construction of a high-speed channel between planets make a decision, the channel can be two-way traffic, however, due to the use of high energy weapons in the war, the space also becomes unstable, in order to prevent turbulence of time and space led to the suspension of a particular channel, need to make sure that in the construction of the main channel must be additional build a auxiliary channel to spare, there are even among the two planets in the immediate vicinity of the channel,

Your task is to help the governor to find solution, least expensive to make all the planets can reach each other and to meet the above conditions,

Enter

Input data for the first behavior two positive integer n, m, n, said the number of planets in galaxies, m said of the available channel number, the next m lines, each line has three positive integers a, b, c, a, b says the ends of the channel, c said to build the cost of the channel,

O

Only one line of output data, the minimum cost to meet the conditions, if did not meet the conditions, the output 1,

The input sample


2, 3,
1 2 1
1 2 3
2 1 2
The output sample


3
Tip

Article 1, built the first and the third channel, one of the family, the other a standby,
2, N<100000, M<2500000
3, can directly connected to show only a channel to each other,