说明

为筹备 20XX 年在 IOI 国举办的奥运会，决定对 IOI 国内的 JOI 公园进行整修。JOI 公园内有 $N$ 个广场，编号为 $1$ 到 $N$。连接这些广场的有 $M$ 条道路，编号为 $1$ 到 $M$。道路 $i$ ($1 \le i \le M$) 双向连接广场 $A_i$ 和广场 $B_i$，长度为 $D_i$。从任何一个广场都可以通过若干条道路到达其他任何广场。

整修计划如下：首先，选择一个非负整数 $X$，然后在所有距离广场 1 不超过 $X$ 的广场（包括广场 1 本身）之间，两两用地下通道连接起来。这里，广场 $i$ 与广场 $j$ 的距离定义为从广场 $i$ 到广场 $j$ 所需经过的道路长度之和的最小值。整修计划中有一个关于地下通道整修成本的整数 $C$。修建这些地下通道的总成本为 $C \times X$。

接着，将所有已被地下通道连接的广场对之间的道路全部拆除。拆除道路不需要成本。

最后，对所有未被拆除而保留下来的道路进行修补。修补一条长度为 $d$ 的道路所需的成本为 $d$。

在整修计划实施前，JOI 公园内没有地下通道。请求出整修 JOI 公园所需的总成本的最小值。

任务

给定 JOI 公园的广场信息以及关于地下通道整修成本的整数，请编写一个程序，计算整修 JOI 公园所需的总成本的最小值。

输入格式

从标准输入读取以下数据。

• 第一行包含三个以空格分隔的整数 $N, M, C$。这表示有 $N$ 个广场，$M$ 条道路，以及地下通道整修成本相关的整数为 $C$。
• 接下来的 $M$ 行中，第 $i$ 行 ($1 \le i \le M$) 包含三个以空格分隔的整数 $A_i, B_i, D_i$。这表示道路 $i$ 连接广场 $A_i$ 和广场 $B_i$，长度为 $D_i$。

输出格式

向标准输出输出一行，包含一个整数，表示整修 JOI 公园所需的总成本的最小值。

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

提示

样例解释 1

在这个样例中，选择 $X = 3$，将所有距离广场 1 不超过 $3$ 的广场（广场 1、广场 2、广场 3）两两用地下通道连接。此时，总成本为 $2 \times 3 + 3 + 5 = 14$。这是最小值。

样例解释 2

在这个样例中，当 $X = 0$ 时，总成本最小。

样例解释 3

在这个样例中，选择 $X = 5$，将所有广场两两用地下通道连接时，总成本最小。

数据范围

所有输入数据满足以下条件：

• $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)$ 且 $(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$)。
• 保证在给定的输入数据中，从任何一个广场都可以通过若干条道路到达其他任何广场。

子任务

子任务 1 [15 分]

满足以下条件：

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

子任务 2 [45 分]

满足以下条件：

• $N \le 100$。
• $M \le 4000$。

子任务 3 [40 分]

没有额外限制。

翻译由 DeepSeek V3.2 完成