## Megacities

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
Problem type

Your boss has left you in charge of cities with forests separating them. Each forest has a cost required to clear, and clearing a forest will merge the two cities it had once separated. He wants you to merge these cities into megacities, where the number of megacities satisfies . What is the minimum cost required to complete the job? If there are two minimum solutions, find the larger one.

#### Input Specifications

The first line will contain two integers, and , separated by a space.

The next lines will contain three integers, , the two cities separated by a forest and the cost to clear the forest, separated by spaces. and are guaranteed to be different from each other.

#### Output Specifications

Output the minimum cost required to complete the job, satisfying the conditions.

#### Sample Input 1

5 7
3 4 23
1 3 18
3 4 2
3 2 14
1 3 3
5 3 6
4 3 3

#### Sample Output 1

25

#### Sample Input 2

4 8
2 1 18
4 2 8
2 4 26
4 1 13
1 4 12
4 1 7
2 4 7
4 2 1

#### Sample Output 2

0