Problem Description

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.

Input Format

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 Format

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

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

14

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

15

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

10

Hint

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