题目描述

译自 JOI 2015 Final T3「JOI 公園」

时值 20XX 年，为了给办奥赛做准备，IOI 国将要修缮 JOI 公园。 JOI 公园里有 $N$ 个广场，这些广场从 $1$ 到 $N$ 编号。有 $M$ 条道路连接各个广场，这些道路从 $1$ 到 $M$ 编号。第 $i$ $(1 \leq i \leq M)$ 条道路是一条连接第 $A_i$ 和第 $B_i$ 个广场的双向边，长度为 $D_i$ 。任意两个广场间一定有道路（直接或间接）相连。

修缮计划如下：

1. 首先，选择一个自然数 $X$ ，将和第一个广场距离等于 $X$ 或在 $X$ 以下的所有广场（含第一个广场）相互之间连结一条地下通道。广场 $i$ 和广场 $j$ 的距离指，从广场 $i$ 到广场 $j$ 经过的道路长度总和的最小值。定义 $C$ 为一个与修筑地下通道花费有关的量（ $C$ 是整数）。修筑所有地下通道的花费为 $C\times X$ 。

2. 接下来，撤去已经通过地下通道连接的广场之间的道路。撤去道路的花费不计。

3. 最后，将没有被撤去的道路进行修补，长为 $d$ 的道路修补的花费为 $d$ 。

修缮计划实施之前， JOI 公园没有地下通道。请求出 JOI 公园修缮花费总和的最小值。

---

任务

给出 JOI 公园的广场间道路的情况和 $C$ 的值，请编写程序求出修缮 JOI 公园的花费总和的最小值。

---

输入格式

• 第一行为三个以空格分开的整数 $N, M, C$ ，分别表示广场共有 $N$ 个，道路有 $M$ 条，而 $C$ 为与修筑地下通道花费有关的量；
• 接下来 $M$ 行中的第 $i$ 行 $(1 \leq i \leq M)$ 为三个以空格分开的整数 $A_i, B_i, D_i$ 。表示第 $i$ 条道路连接广场 $A_i$ 和广场 $B_i$ ，其长度为 $D_i$ 。

---

输出格式

输出一行一个整数：修缮 JOI 公园的花费总和的最小值。

---

样例 1

输入

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

输出

14

解释： 对于输入样例 1， $X=3$ 也就是说，和广场 $1$ 的距离在 $3$ 或以下的广场（广场 $1$ ，广场 $2$ ，广场 $3$ ）互相之间连接一条地下通道。修缮总花费为 $2\times 3+3+5=14$ 。这就是最小值。

---

样例 2

输入

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

输出

15

对于输入样例 2 ，$X=0$ 时修缮总花费最小。

---

样例 3

输入

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

输出

10

对于输入样例 3，$X=5$ 时所有广场相互间都会连接一条地下通道，此时修缮的花费最小。

---

数据范围与提示

对于 $15\%$ 的分值：

• $N \leq 100$
• $M \leq 200$
• $C \leq 100$
• $D_i \leq 10$ $(1 \leq i \leq M)$

对于另 $45\%$ 的分值：

• $N \leq 100$
• $M \leq 4000$

对于 $100\%$ 的分值，所有输入数据满足以下条件：

• $2 \leq N \leq 10^5$
• $1 \leq M \leq 2\times 10^5$
• $1 \leq C \leq 10^5$
• $1 \leq A_i, B_i \leq N$ $(1 \leq i \leq M)$
• $A_i \not = B_i$ $(1 \leq i \leq M)$
• $(A_i, B_i) \not = (A_j, B_j)$ 而且 $(A_i, B_i) \not = (B_j, A_j)$ $(1 \leq i \lt j \leq M)$
• $1 \leq D_i \leq 10^5$ $(1 \leq i \leq M)$

输入数据保证任意两个广场之间一定有道路连接（直接或间接）。