P15818 [JOI 2015 Final] JOI Park / JOI Park

To prepare for the Olympics to be held in IOI Country in 20XX, it has been decided to renovate JOI Park in IOI Country. There are $N$ squares in JOI Park, numbered from $1$ to $N$. There are $M$ roads connecting these squares, numbered from $1$ to $M$. Road $i$ ($1 \le i \le M$) bidirectionally connects square $A_i$ and square $B_i$, and its length is $D_i$. From any square, you can reach any other square by traveling along some roads. The renovation plan is as follows: First, choose a non-negative integer $X$. Then, between every pair of squares whose **distance from square 1 is at most $X$** (including square 1 itself), connect them with an underground passage. Here, the distance between square $i$ and square $j$ is defined as the minimum possible sum of road lengths along a route from square $i$ to square $j$. In the renovation plan, there is an integer $C$ related to the cost of building underground passages. The total cost to build these underground passages is $C \times X$. Next, remove all roads between every **pair of squares that are connected by underground passages**. Removing roads costs nothing. Finally, repair all roads that are **not removed and remain**. The cost to repair a road of length $d$ is $d$. Before the plan is carried out, there are no underground passages in JOI Park. Find the minimum total cost required to renovate JOI Park. ### Task Given the information about the squares and roads in JOI Park, and the integer related to the underground passage cost, write a program to compute the minimum total cost required to renovate JOI Park.

Read the following data from standard input. * The first line contains three integers $N, M, C$ separated by spaces. This means there are $N$ squares, $M$ roads, and the integer related to the underground passage renovation cost is $C$. * Each of the next $M$ lines, line $i$ ($1 \le i \le M$), contains three integers $A_i, B_i, D_i$ separated by spaces. This means road $i$ connects square $A_i$ and square $B_i$, and its length is $D_i$.

Output one line to standard output containing one integer, which is the minimum total cost required to renovate JOI Park.

### Sample Explanation 1 In this sample, choose $X = 3$, and connect every pair of squares whose distance from square 1 is at most $3$ (squares 1, 2, and 3) with underground passages. Then the total cost is $2 \times 3 + 3 + 5 = 14$. This is the minimum value. ### Sample Explanation 2 In this sample, the total cost is minimized when $X = 0$. ### Sample Explanation 3 In this sample, the total cost is minimized when choosing $X = 5$ and connecting every pair of squares with underground passages. ### Constraints All input data satisfy the following conditions: * $2 \le N \le 100000$. * $1 \le M \le 200000$. * $1 \le C \le 100000$. * $1 \le A_i \le N$ ($1 \le i \le M$). * $1 \le B_i \le N$ ($1 \le i \le M$). * $A_i \ne B_i$ ($1 \le i \le M$). * $(A_i, B_i) \ne (A_j, B_j)$ and $(A_i, B_i) \ne (B_j, A_j)$ ($1 \le i < j \le M$). (That is, there are no multiple edges, and the edges are undirected.) * $1 \le D_i \le 100000$ ($1 \le i \le M$). * It is guaranteed that in the given input data, from any square you can reach any other square by traveling along some roads. ### Subtasks #### Subtask 1 [15 points] Satisfies the following conditions: * $N \le 100$. * $M \le 200$. * $C \le 100$. * $D_i \le 10$ ($1 \le i \le M$). #### Subtask 2 [45 points] Satisfies the following conditions: * $N \le 100$. * $M \le 4000$. #### Subtask 3 [40 points] No additional constraints. Translated by DeepSeek V3.2. Translated by ChatGPT 5