#2726. 「JOI 2015 Final」JOI 公园

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

题目描述

译自 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

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)
  • 输入数据保证任意两个广场之间一定有道路连接(直接或间接)。