## Megacities

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.

#### Subtasks

##### Subtask 1 [20%]

##### Subtask 2 [80%]

No additional constraints.

#### 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`

## Comments