2726 「JOI 2015 Final」JOI 公园

译自 JOI 2015 Final T3「JOI 公園」

时值 20XX 年，为了给办奥赛做准备，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$， $ X=3 $ 也就是说，和广场 $ 1 $ 的距离在 $ 3 $ 或以下的广场（广场 $ 1 $ ，广场 $ 2 $ ，广场 $ 3 $ ）互相之间连接一条地下通道。修缮总花费为 $ 2\times 3+3+5=14 $ 。这就是最小值。

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

对于输入样例 $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) $ - 输入数据保证任意两个广场之间一定有道路连接（直接或间接）。