配点: 100 点
为了准备在20XX年于IOI国举办的奥林匹克,决定整备位于IOI国的JOI公园。JOI公园里 N 方格,并且有 它的编号为 1 我决定将所有值添加到 N 。连接广场 M 有一条书路,路是 它的编号为 1 我决定将所有值添加到 M 。路 i (1 \leqq i \leqq M) 是一个正方形 A_i 和正方形 B_i 双向连接,长度为 D_i 。您可以沿着几条路径从任何方块到任何方块。
在维护计划中,首先, 大于或等于0 的整数 选择 X 并方形 与 1 的距离是 X 下面是一个正方形(正方形 1 )都通过地下通道相互连接。然而,广场 i 和正方形 j 的距离是平方 i 卡拉广场 这是前往 j 时所经过的道路长度总和的最小值。维护计划中,与地下通道的建设成本相关的整数。 C 已修复。修建地下通道的费用为 C \times X 。
接下来,所有通过地下通道连接广场的道路将被拆除。清理道路不需要任何费用。
最后,修复所有未拆除的剩余道路。长度 修复 d 道路的费用为 d 。
维护计划实施前,JOI公园内没有地下通道。求维护 JOI 公园所需成本总和的最小值。
課題
给定 JOI 公园广场的信息以及与地下通道建设成本相关的整数,编写一个程序,找出 JOI 公园建设成本总和的最小值。
入力
从标准输入读取以下数据。
- 1 行包含一个整数 N, M, C 以空格作为分隔符。这是因为正方形是 N 这条路是 M 有一本书,与地下通道维护成本相关的整数是 C 。
- 继续 M 行 i 行目 (1 \leqq i \leqq M) 是一个整数 A_i, B_i, D_i 以空格作为分隔符。这就是路 i 是正方形 A_i 和正方形 B_i 长度是 D_i 。
出力
表示 JOI 公园维护成本最小总和的整数被输出到标准输出。 输出为 1 行。
制限
所有输入数据满足以下条件。
- 2 \leqq N \leqq 100\,000.
- 1 \leqq M \leqq 200\,000.
- 1 \leqq C \leqq 100\,000.
- 1 \leqq A_i \leqq N (1 \leqq i \leqq M).
- 1 \leqq B_i \leqq N (1 \leqq i \leqq M).
- A_i \neq B_i (1 \leqq i \leqq M).
- (A_i, B_i) \neq (A_j, B_j) 以及 (A_i, B_i) \neq (B_j, A_j) (1 \leqq i < j \leqq M).
- 1 \leqq D_i \leqq 100\,000 (1 \leqq i \leqq M).
- 给定输入数据,保证您可以通过遵循某些路径从任何方格到达任何方格。
小課題
小課題 1 [15 点]
满足以下条件。
- N \leqq 100.
- M \leqq 200.
- C \leqq 100.
- D_i \leqq 10 (1 \leqq i \leqq M).
小課題 2 [45 点]
满足以下条件。
- N \leqq 100.
- M \leqq 4\,000.
小課題 3 [40 点]
没有其他限制。
入力例 1
5 5 2 2 3 1 3 1 2 2 4 3 1 2 4 2 5 5
出力例 1
14
在此输入示例中,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
在此输入示例中,X = 0 维护成本总和最小化。
入力例 3
6 5 2 1 2 2 1 3 4 1 4 3 1 5 1 1 6 5
出力例 3
10
在此输入示例中,X = 5 当所有广场通过地下通道相互连接时,维护成本的总和将最小化。