#2726. 「JOI 2015 Final」JOI 公园

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: hy1004

题目描述

译自 JOI 2015 Final T3「JOI 公園

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

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

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

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

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

任务

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

输入格式

第一行为三个以空格分开的整数 N,M,C N,M,C ,分别表示广场共有 N N 个,道路有 M M 条,而 C C 为与修筑地下通道花费有关的量;
接下来 M M 行中的第 i i (1iM) (1 \leq i \leq M) 为三个以空格分开的整数 Ai,Bi,Di A_i,B_i,D_i 。表示第 i i 条道路连接广场 Ai A_i 和广场 Bi B_i ,其长度为 Di 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

对于输入样例 11X=3 X=3 也就是说,和广场 1 1 的距离在 3 3 或以下的广场(广场 1 1 ,广场 2 2 ,广场 3 3 )互相之间连接一条地下通道。修缮总花费为 2×3+3+5=14 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 2 X=0 X=0 时修缮总花费最小。

输入样例 3

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

输出样例 3

10

样例说明 3

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

数据范围与提示

对于 15% 15\% 的分值:

  • N100 N \leq 100
  • M200 M \leq 200
  • C100 C \leq 100
  • Di10(1iM) D_i \leq 10 (1 \leq i \leq M)

对于另 45% 45\% 的分值:

  • N100 N \leq 100
  • M4000 M \leq 4000

对于 100% 100\% 的分值,所以输入数据满足以下条件:

  • 2N105 2 \leq N \leq 10^5
  • 1M2×105 1 \leq M \leq 2\times 10^5
  • 1C105 1 \leq C \leq 10^5
  • 1Ai,BiN(1iM) 1 \leq A_i,B_i \leq N (1 \leq i \leq M)
  • Ai=Bi(1iM) A_i\not = B_i (1 \leq i \leq M)
  • (Ai,Bi)=(Aj,Bj) (A_i,B_i)\not =(A_j,B_j) 而且 (Ai,Bi)=(Bj,Aj)(1i<jM) (A_i,B_i)\not =(B_j,A_j) (1 \leq i\lt j \leq M)
  • 1Di105(1iM) 1 \leq D_i \leq 10^5 (1 \leq i \leq M)
  • 输入数据保证任意两个广场之间一定有道路连接(直接或间接)。