题目描述

为筹备 20XX 年在 IOI 国举办的奥运会，决定对 IOI 国内的公园进行整修。公园内有 $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$。

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

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

输入格式

第一行包含三个以空格分隔的整数 $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$。

输出格式

输出一行，一个整数，表示整修公园所需的总成本的最小值。

样例输入 1

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

样例输出 1

14

样例输入 2

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

样例输出 2

15

样例输入 3

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

样例输出 3

10

说明

样例解释

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

其它样例说明

• 样例 $4$：见选手目录下的 park/park4.in 与 park/park4.ans，该测试用例满足测试点编号 $1\sim 5$ 的约束条件。
• 样例 $5$：见选手目录下的 park/park5.in 与 park/park5.ans，该测试用例满足测试点编号 $6\sim 12$ 的约束条件。
• 样例 $6$：见选手目录下的 park/park6.in 与 park/park6.ans，该测试用例满足测试点编号 $13\sim 20$ 的约束条件。

数据范围

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

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

各测试点的附加限制如下表所示：

点击下载大样例