P15818 [JOI 2015 Final] JOI 公园 / JOI Park

为筹备 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 公园所需的总成本的最小值。

### 样例解释 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 完成