JOI 公园整备计划

为了备战 20XX 年在 IOI 国举办的奥林匹克运动会，决定对 IOI 国的 JOI 公园进行整备。JOI 公园里有 N 个广场，每个广场都有一个从 1 到 N 的编号。公园中有 M 条道路，每条道路都有一个从 1 到 M 的编号。道路 i (1 ≤ i ≤ M) 双向连接着广场 A[i] 和广场 B[i]，长度为 D[i]。从任何一个广场出发都可以通过若干条道路到达另一个广场。

整备计划的第一步是选择一个非负整数 X，用地下通道连接所有距离广场 1 不超过 X 的广场（包括广场 1 自身）。其中，广场 i 和广场 j 的距离定义为从广场 i 到广场 j 的最短路径长度之和。整备计划还确定了与地下通道建设成本相关的整数 C。地下通道的建设成本为 C × X。

接下来，移除连接相连广场的所有道路。移除道路不需要花费。最后，修复所有未被移除的道路。修复长度为 d 的道路需要花费 d。

求整备前 JOI 公园的最小整备成本总和。

问题

给定 JOI 公园的广场信息和地下通道建设成本，编写一个程序求 JOI 公园的最小整备成本总和。

---

输入

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

• 第一行包含三个整数 N、M 和 C，以空格分隔。表示公园中有 N 个广场，M 条道路，地下通道的建设成本为 C。
• 接下来的 M 行中的第 i 行（1 ≤ i ≤ M）包含三个整数 A[i]、B[i] 和 D[i]，以空格分隔。表示道路 i 连接广场 A[i] 和广场 B[i]，长度为 D[i]。

输出

在标准输出中，以一行输出 JOI 公园的最小整备成本总和。

---

限制

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

• 2 ≤ N ≤ 100,000。
• 1 ≤ M ≤ 200,000。
• 1 ≤ C ≤ 100,000。
• 1 ≤ A[i] ≤ N（1 ≤ i ≤ M）。
• 1 ≤ B[i] ≤ N（1 ≤ i ≤ M）。
• A[i] ≠ B[i]（1 ≤ i ≤ M）。
• (A[i], B[i]) ≠ (A[j], B[j]) 且 (A[i], B[i]) ≠ (B[j], A[j])（1 ≤ i < j ≤ M）。
• 1 ≤ D[i] ≤ 100,000（1 ≤ i ≤ M）。
• 根据给定的输入数据，保证从任何一个广场都可以通过若干条道路到达其他任何一个广场。

---

示例 1

输入：

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

输出：

14

对于这个示例，如果选择 X = 3，将广场 1 到广场 3（包括广场 1 和广场 3）相互连接起来，整备的成本总和为 2 × 3 + 3 + 5 = 14，这是最小值。

---

示例 2

输入：

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

输出：

15

对于这个示例，当 X = 0 时，整备的成本总和最小。

---

示例 3

输入：

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

输出：

10

对于这个示例，将所有的广场通过地下通道连接起来时，整备的成本总和最小。