「JOI 2014/2015 决赛」JOI 公园

译自 JOI 2014/2015 决赛 T3「JOI 公園」

题目描述

时值 $20\text{XX}$ 年， IOI 国为了给办奥赛做准备，将要修缮 IOI 国中的 JOI 公园。 JOI 公园里有 $N$ 个广场，这些广场从 $1$ 到 $N$ 编号。有 $M$ 条道路连接各个广场，这些道路从 $1$ 到 $M$ 编号。第 $i(1 \leq i \leq M)$ 条道路是一条连接第 $A_i$ 和第 $B_i$ 个广场的双向边，长度为 $D_i$ 。任意两个广场间一定有道路（直接或间接）相连。

修缮计划如下：首先，选择一个自然数 $X$ ，将和第一个广场距离等于 $X$ 或在 $X$ 以下的所有广场（含第一个广场）相互之间连结一条地下通道。广场 $i$ 和广场 $j$ 的距离指，从广场 $i$ 到广场 $j$ 经过的道路长度总和的最小值。定义 $C$ 为一个与修筑地下通道花费有关的量（ $C$ 是整数）。修筑所有地下通道的花费为 $C\times X$ 。

接下来，撤去已经通过地下通道连接的广场之间的道路。撤去道路的花费不计。

最后，将没有被撤去的道路进行修补，长为 $d$ 的道路修补的花费为 $d$ 。

修缮计划实施之前， JOI 公园没有地下通道。请求出 JOI 公园修缮花费总和的最小值。

任务

给出 JOI 公园的广场间道路的情况和 $C$ 的值，请编写程序求出修缮 JOI 公园的花费总和的最小值。

输入格式

输入标准如下：

• 第一行为三个以空格分开的整数 $N,M,C$ ，分别表示广场共有 $N$ 个，道路有 $M$ 条，而 $C$ 为与修筑地下通道花费有关的量；
• 接下来 $M$ 行中的第 $i$ 行 $(1 \leq i \leq M)$ 为三个以空格分开的整数 $A_i,B_i,D_i$ 。表示第 $i$ 条道路连接广场 $A_i$ 和广场 $B_i$ ，其长度为 $D_i$ 。

输出格式

输出一行一个整数：修缮 JOI 公园的花费总和的最小值。

样例

输入样例 1

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

输出样例 1

14

样例说明 1

对于输入样例 $1$， $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

样例说明 2

对于输入样例 $2$ ，$X=0$ 时修缮总花费最小。

输入样例 3

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

输出样例 3

10

样例说明 3

对于输入样例 $3$，$X=5$ 时所有广场相互间都会连接一条地下通道，此时修缮的花费最小。

数据范围

对于 $15\%$ 的分值：

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

对于另 $45\%$ 的分值：

• $N \leq 100$
• $M \leq 4000$

对于 $100\%$ 的分值，所以输入数据满足以下条件：

• $2 \leq N \leq 10^5$
• $1 \leq M \leq 2\times 10^5$
• $1 \leq C \leq 10^5$
• $1 \leq A_i,B_i \leq N (1 \leq i \leq M)$
• $A_i\not = B_i (1 \leq i \leq M)$
• $(A_i,B_i)\not =(A_j,B_j)$ 而且 $(A_i,B_i)\not =(B_j,A_j) (1 \leq i\lt j \leq M)$
• $1 \leq D_i \leq 10^5 (1 \leq i \leq M)$
• 输入数据保证任意两个广场之间一定有道路连接（直接或间接）。

感谢@ミク 提供的翻译