In preparation for the Olympics to be held in the country of IOI in 20XX, it has been decided to renovate the JOI Park in the country of IOI. The JOI Park has $N$ squares, numbered from $1$ to $N$. There are $M$ roads connecting the squares, numbered from $1$ to $M$. Road $i$ ($1 \le i \le M$) connects square $A_i$ and square $B_i$ in both directions, and its length is $D_i$. It is possible to travel from any square to any other square by following some roads.

The renovation plan is as follows: First, choose an integer $X \ge 0$, and connect all squares whose distance from square $1$ is at most $X$ (including square $1$) to each other with underground passages. Here, the distance between square $i$ and square $j$ is the minimum sum of the lengths of the roads one must traverse to go from square $i$ to square $j$. An integer $C$ related to the cost of constructing underground passages is fixed in the renovation plan. The cost of constructing the underground passages is $C \times X$.

Next, remove all roads that connect squares that are now connected by underground passages. There is no cost for removing roads.

Finally, repair all roads that remain after the removal. The cost to repair a road of length $d$ is $d$.

There are no underground passages in the JOI Park before the renovation plan is implemented. Find the minimum total cost of the renovation of the JOI Park.

Input

Read the following data from standard input:

• The first line contains three space-separated integers $N, M, C$. This indicates that there are $N$ squares, $M$ roads, and the integer $C$ related to the cost of constructing underground passages.
• The $i$-th line of the following $M$ lines ($1 \le i \le M$) contains three space-separated integers $A_i, B_i, D_i$. This indicates that road $i$ connects square $A_i$ and square $B_i$ and has a length of $D_i$.

Output

Output the minimum total cost of the renovation of the JOI Park as an integer on a single line.

Constraints

All input data satisfy the following conditions:

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

Subtasks

Subtask 1 [15 points]

The following conditions are satisfied: $N \le 100$. $M \le 200$. $C \le 100$. $D_i \le 10$ ($1 \le i \le M$).

Subtask 2 [45 points]

The following conditions are satisfied: $N \le 100$. $M \le 4\,000$.

Subtask 3 [40 points]

There are no additional constraints.

Examples

Input 1

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

Output 1

14

Note 1

In this example, by setting $X = 3$, all squares whose distance from square $1$ is at most $3$ (square $1$, square $2$, square $3$) are connected to each other with underground passages. The total cost of the renovation is $2 \times 3 + 3 + 5 = 14$. This is the minimum value.

Input 2

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

Output 2

15

Note 2

In this example, the total cost of the renovation is minimized when $X = 0$.

Input 3

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

Output 3

10

Note 3

In this example, the total cost of the renovation is minimized when $X = 5$, connecting all squares to each other with underground passages.