PROGRAMMING:Build a plank road in the open
Han Xin is valued by Liu Bang for his talent. Now, his boss has a problem to solve
There are $$n $$cities and $$M $$two-way roads, each of which has a certain length. It is guaranteed that any two cities will be directly or indirectly connected
Now, Han Xin has a right of choice. He can choose a positive integer $$t $$, $$t $$, which means to build an underground passage between all squares with the minimum distance of < = $$t $$from the city numbered $$1 $$. Liu Bang himself will give a positive integer $$C $$, so the cost of building all underground passages is $$t $$* $$C $$
Hanxin then landfills all the urban roads that have been connected by underground passages. The cost of these roads is negligible
Finally, the total cost is the sum of the cost of building underground passage and the cost of road not buried
Now, Han Xin wants to ask for the minimum cost
###Input format:
The first line gives three positive integers, $$n $, $$M $, $$C $$. Denotes $$n $$cities and $$M $$roads, as well as the cost constant C for the construction of underpass
In the following $$M $$line, each line gives three positive integers $$u $, $$V $, $$W $$, indicating that there is a road of length of $$W $$between city $$u $$and city $$V $$
Ensure that there are no double edges and self loops
2<=$$n$$<=100000,1<=$$m$$<=200000,1<=$$c$$,$$w$$<=100000
###Output format:
Output a positive integer on a line, indicating the minimum cost
###Input example:
Here is a set of inputs. For example:
```in
5 5 2
2 3 1
3 1 2
2 4 3
1 2 4
2 5 5
```
###Output example:
The corresponding output is given here. For example:
```out
fourteen
```
Example description: for this example, let's take x = 3, then there are 2,3 cities which are 3 or less away from city 1. Then the first, second and fourth edges will be buried, and the cost is 2 * 3 + 3 + 5 = 14. This is the minimum cost
answer：If there is no answer, please comment
There are $$n $$cities and $$M $$two-way roads, each of which has a certain length. It is guaranteed that any two cities will be directly or indirectly connected
Now, Han Xin has a right of choice. He can choose a positive integer $$t $$, $$t $$, which means to build an underground passage between all squares with the minimum distance of < = $$t $$from the city numbered $$1 $$. Liu Bang himself will give a positive integer $$C $$, so the cost of building all underground passages is $$t $$* $$C $$
Hanxin then landfills all the urban roads that have been connected by underground passages. The cost of these roads is negligible
Finally, the total cost is the sum of the cost of building underground passage and the cost of road not buried
Now, Han Xin wants to ask for the minimum cost
###Input format:
The first line gives three positive integers, $$n $, $$M $, $$C $$. Denotes $$n $$cities and $$M $$roads, as well as the cost constant C for the construction of underpass
In the following $$M $$line, each line gives three positive integers $$u $, $$V $, $$W $$, indicating that there is a road of length of $$W $$between city $$u $$and city $$V $$
Ensure that there are no double edges and self loops
2<=$$n$$<=100000,1<=$$m$$<=200000,1<=$$c$$,$$w$$<=100000
###Output format:
Output a positive integer on a line, indicating the minimum cost
###Input example:
Here is a set of inputs. For example:
```in
5 5 2
2 3 1
3 1 2
2 4 3
1 2 4
2 5 5
```
###Output example:
The corresponding output is given here. For example:
```out
fourteen
```
Example description: for this example, let's take x = 3, then there are 2,3 cities which are 3 or less away from city 1. Then the first, second and fourth edges will be buried, and the cost is 2 * 3 + 3 + 5 = 14. This is the minimum cost
answer：If there is no answer, please comment