Problem Description

In the year 20XX, preparations are being made for the Olympics to be held in the IOI country. As part of these preparations, the JOI Park in IOI country needs to be renovated. JOI Park has \( N \) squares, numbered from 1 to \( N \). There are \( M \) paths connecting these squares, numbered from 1 to \( M \). Path \( i \) (for \( 1 \leq i \leq M \)) connects square \( A_i \) and square \( B_i \) bidirectionally, with a length of \( D_i \). It is possible to travel from any square to any other square by traversing some paths.

The renovation plan involves first selecting an integer \( X \) (where \( X \geq 0 \)) and connecting all squares whose distance from square 1 is \( X \) or less (including square 1) with underground tunnels. The distance between square \( i \) and square \( j \) is defined as the minimum sum of the lengths of the paths needed to travel from square \( i \) to square \( j \). The cost of constructing these underground tunnels is \( C \times X \), where \( C \) is a given integer related to the cost of constructing the tunnels.

Next, all paths connecting the squares that are now linked by underground tunnels are removed. There is no cost associated with removing these paths.

Finally, the remaining paths that were not removed are repaired. The cost of repairing a path of length \( d \) is \( d \).

There are no underground tunnels in JOI Park before the renovation plan is implemented. Determine the minimum total cost required to renovate JOI Park.

Input Format

Read the following data from standard input:

• The first line contains three integers \( N \), \( M \), and \( C \), separated by spaces. These represent the number of squares, the number of paths, and the cost factor for constructing underground tunnels, respectively.
• The next \( M \) lines contain three integers each: \( A_i \), \( B_i \), and \( D_i \), separated by spaces. These describe path \( i \) connecting square \( A_i \) and square \( B_i \) with a length of \( D_i \).

Output Format

Output a single integer on one line to standard output, representing the minimum total cost required to renovate JOI Park.

Sample Input and Output

Sample Input #1

5 5 2
2 3 1
3 1 2
2 4 3
1 2 4
2 5 5

Sample Output #1

14

Sample Input #2

5 4 10
1 2 3
2 3 4
3 4 3
4 5 5

Sample Output #2

15

Sample Input #3

6 5 2
1 2 2
1 3 4
1 4 3
1 5 1
1 6 5

Sample Output #3

10

Notes/Hints

Task

Given the information about the squares in JOI Park and the cost factor for constructing underground tunnels, create a program to determine the minimum total cost required to renovate JOI Park.

Constraints

All input data satisfies the following conditions:

• \( 2 \leq N \leq 100,000 \).
• \( 1 \leq M \leq 200,000 \).
• \( 1 \leq C \leq 100,000 \).
• \( 1 \leq A_i \leq N \) (for \( 1 \leq i \leq M \)).
• \( 1 \leq B_i \leq N \) (for \( 1 \leq i \leq M \)).
• \( A_i \neq B_i \) (for \( 1 \leq i \leq M \)).
• \( (A_i, B_i) \neq (A_j, B_j) \) and \( (A_i, B_i) \neq (B_j, A_j) \) (for \( 1 \leq i < j \leq M \)).
• \( 1 \leq D_i \leq 100,000 \) (for \( 1 \leq i \leq M \)).
• It is guaranteed that in the given input data, it is possible to travel from any square to any other square by traversing some paths.

Subtasks

Subtask 1 [15 points]

Satisfies the following conditions:

• \( N \leq 100 \).
• \( M \leq 200 \).
• \( C \leq 100 \).
• \( D_i \leq 10 \) (for \( 1 \leq i \leq M \)).

Subtask 2 [45 points]

Satisfies the following conditions:

• \( N \leq 100 \).
• \( M \leq 4,000 \).

Subtask 3 [40 points]

No additional constraints.

Sample Explanation 1

In this input example, choosing \( X = 3 \) and connecting all squares within a distance of 3 from square 1 (squares 1, 2, and 3) with underground tunnels results in a total renovation cost of \( 2 \times 3 + 3 + 5 = 14 \). This is the minimum cost.

Sample Explanation 2

In this input example, the minimum total renovation cost is achieved when \( X = 0 \).

Sample Explanation 3

In this input example, choosing \( X = 5 \) and connecting all squares with underground tunnels results in the minimum total renovation cost.

见题面 Input 部分

见题面 Output 部分