## OCC '19 G5 - King kobortor's Infrastructure

View as PDF

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 512M

Author:
Problem type

King kobortor, 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 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 kobortor has the superpower to upgrade the roads around a city to weight . However, using this superpower on cities will cost . Please help King kobortor 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.

#### 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 kobortor can apply the superpower on city or to get a total cost of .

In the sample case, King kobortor 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 .