为了准备 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 公园所需成本之和的最小值。

输入格式

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

• 第 1 行包含三个整数 $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 公园所需成本之和的最小值作为一个整数输出到标准输出。

数据范围

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

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

子任务

子任务 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 4\,000$

子任务 3 [40 点]

无附加限制。

样例

输入 1

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

输出 1

14

说明：在该样例中，取 $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

输出 2

15

说明：在该样例中，$X = 0$ 时整修成本之和最小。

输入 3

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

输出 3

10

说明：在该样例中，取 $X = 5$，将所有广场通过地下通道相互连接，整修成本之和最小。