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.
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 .
One integer, the minimum sum of costs.
Sample Input 1
2 1 1 2 58
Sample Output 1
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
Explanation to Sample Output
In the sample case, King Kobortor can apply the superpower on city or to get a total cost of 10.
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 .
For all test cases, , , and .
|No additional constraints.|