City Division Plan

A village has N houses and M bidirectional roads. Each road has a maintenance cost, and in the given village there is always a path between any two houses.

The village will be divided into exactly two separate villages. Each of the two villages must contain at least one house, and within each village every pair of houses must remain connected by some path.

After the division, every road connecting the two different villages can be removed. Inside each village, additional unnecessary roads may also be removed as long as that village remains connected. Find the minimum possible sum of maintenance costs of the roads that remain.

The first line contains the number of houses N and the number of roads M. N is an integer between 2 and 100,000 inclusive, and M is an integer between 1 and 1,000,000 inclusive.

Each of the next M lines contains three integers A B C, describing a bidirectional road between house A and house B with maintenance cost C. C is an integer between 1 and 1,000 inclusive.

The given graph is always connected.

Print the minimum possible sum of maintenance costs of the roads that remain after removing roads while satisfying the conditions.