King cities (), and () bidirectional roads, where the road connects cities and () with weight (). There may be multiple roads between cities and . Suppose that the country is connected. The cost of bad infrastructure is the weight of the largest road in the country. King has the superpower to upgrade the roads around a city to weight . However, using this superpower on cities will cost . Please help King to find out the minimum sum of costs. The sum of costs includes the cost of the largest road and the cost of using the superpower.

, the ruler of HillThorn, feels the infrastructure in his country is too old. So, he wants to upgrade the infrastructure. HillThorn is a country with#### Constraints

For all subtasks:

Subtask | Points | Additional constraints |
---|---|---|

No additional constraints. |

#### Input Specification

The first line contains two integers, and , the number of cities and the number of roads.

Each of the following lines contains three integers, and , a road connecting cities and with weight .

#### Output Specification

One integer, the minimum sum of costs.

#### Sample Input 1

```
2 1
1 2 58
```

#### Sample Output 1

`10`

#### Sample Input 2

```
6 10
5 6 901
2 6 173
3 5 610
3 5 598
1 5 142
1 2 699
1 5 904
2 4 633
3 6 6
1 4 573
```

#### Sample Output 2

`96`

#### Explanation for Sample Output

In the sample case, King can apply the superpower on city or to get a total cost of .

In the sample case, King can apply the superpower on cities , , and with a cost of and then the largest road is between cities and with a cost of . Thus the total cost is .

## Comments