JOI Park

As part of the preparation for the olympics held in the IOI country in 20XX, JOI park is going to be renovated. JOI park has $N$ squares, numbered 1 to $N$. The park also has $M$ roads that join the squares, numbered 1 to $M$. Road $i$ ($1 \le i \le M$) joins square $A_i$ and square $B_i$ in both directions, and its length is $D_i$. From any square you can reach every other square by following roads.

The renovation plan goes as follows. A value $C$ for the subway construction is given. First, pick an integer $X$ that is at least 0 and join by subway every square whose distance from square 1 is at most $X$, square 1 included. The distance between square $i$ and square $j$ is the smallest sum of road lengths over the routes from square $i$ to square $j$. The subway construction costs $C \times X$ in total.

Next, tear down every road that joins two squares linked by the subway. Tearing down a road is free.

Finally, repair every road left standing. Repairing a road of length $d$ costs $d$.

JOI park has no subway before the renovation starts. Given the squares and roads of JOI park together with the value for the subway construction, write a program that computes the smallest cost of renovating JOI park.

Standard input holds the following information.

• The first line holds the integers $N$, $M$, $C$, separated by spaces. The park has $N$ squares and $M$ roads, and the value for the subway construction is $C$.
• Each of the next $M$ lines holds the integers $A_i$, $B_i$, $D_i$ ($1 \le i \le M$), separated by spaces. Road $i$ joins square $A_i$ and square $B_i$, and its length is $D_i$.

Print the smallest cost of renovating JOI park on one line.

• $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$)
• $1 \le D_i \le 100000$ ($1 \le i \le M$)
• From any square you can reach every other square by following roads.