JOI Park

Interview

Time limit1sMemory limit256 MB

Summary

Pick a distance X from square 1 to minimize C times X plus the total length of roads not fully inside the X radius.

Level: Medium6 of 10
Topics: Shortest path, Sorting, Prefix sum
Solved: No attempts yet

Problem

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.

Input

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$ .

Output

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

Constraints

$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.

Examples3

Example 1
Input
```
5 5 2
2 3 1
3 1 2
2 4 3
1 2 4
2 5 5
```
Expected output
```
14
```
Example 2
Input
```
5 4 10
1 2 3
2 3 4
3 4 3
4 5 5
```
Expected output
```
15
```
Example 3
Input
```
6 5 2
1 2 2
1 3 4
1 4 3
1 5 1
1 6 5
```
Expected output
```
10
```