D - 通信ネットワークの構築 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は通信会社のネットワーク設計担当者です。N 個の拠点があり、それらを結ぶ M 本の通信ケーブルの敷設候補があります。各候補 i は拠点 u_i と拠点 v_i を双方向に結び、敷設コストは c_i です。

高橋君はすべての拠点間で（直接または中継によって）通信可能なネットワークを構築しなければなりません。ただし、ネットワーク全体の評価値は単なる総コストではなく、以下のように定義される「負荷指数」で測られます。

敷設するケーブルの集合を S としたとき、負荷指数は次のように定義されます。

\text{負荷指数} = \left( \sum_{i \in S} c_i \right) + K \times \max_{i \in S} c_i

ここで K は会社の方針で定められた非負整数の係数です。負荷指数は、総敷設コストに加えて、最もコストの高いケーブルのコストに K を掛けたペナルティが加算されることを意味します。これは、極端にコストの高いケーブルを含むことによる保守・運用上のリスクを反映しています。

高橋君は、すべての拠点間を通信可能にするケーブルの集合 S のうち、負荷指数を最小化したいと考えています。負荷指数の最小値を求めてください。

なお、すべての拠点間を通信可能にするケーブルの集合が必ず存在することが保証されます。

制約

  • 2 \leq N \leq 2 \times 10^5
  • N - 1 \leq M \leq 2 \times 10^5
  • 0 \leq K \leq 10^6
  • 1 \leq u_i, v_i \leq N
  • u_i \neq v_i
  • 1 \leq c_i \leq 10^6
  • 入力はすべて整数である
  • すべての拠点間を通信可能にするケーブルの集合が存在する

入力

N M K
u_1 v_1 c_1
u_2 v_2 c_2
:
u_M v_M c_M
  • 1 行目には、拠点の数を表す N 、ケーブル候補の数を表す M 、係数を表す K が、スペース区切りで与えられる。
  • 2 行目から M 行では、各ケーブル候補の情報が与えられる。
  • 1 + i 行目では、ケーブル候補 i が結ぶ 2 つの拠点 u_i , v_i と敷設コスト c_i が、スペース区切りで与えられる。

出力

負荷指数の最小値を 1 行で出力せよ。

入力例 1

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

出力例 1

22

入力例 2

3 3 0
1 2 7
2 3 2
1 3 5

出力例 2

7

入力例 3

8 12 5
1 2 4
1 3 8
2 3 3
2 4 7
3 5 6
4 5 2
4 6 9
5 6 5
5 7 10
6 8 4
7 8 1
3 8 12

出力例 3

55

入力例 4

12 20 100
1 2 15
2 3 18
3 4 14
4 5 16
5 6 20
6 7 13
7 8 17
8 9 19
9 10 12
10 11 21
11 12 11
1 6 50
2 7 45
3 8 40
4 9 35
5 10 30
6 11 25
7 12 22
1 12 100
3 10 28

出力例 4

2276

入力例 5

2 1 1000000
1 2 1000000

出力例 5

1000001000000

Score : 400 pts

Problem Statement

Takahashi is a network design engineer at a telecommunications company. There are N bases, and there are M candidate communication cables to connect them. Each candidate i bidirectionally connects base u_i and base v_i with an installation cost of c_i.

Takahashi must construct a network where all bases can communicate with each other (either directly or via relays). However, the overall evaluation of the network is not measured simply by the total cost, but by a "load index" defined as follows.

Let S be the set of cables to be installed. The load index is defined as:

\text{Load Index} = \left( \sum_{i \in S} c_i \right) + K \times \max_{i \in S} c_i

Here, K is a non-negative integer coefficient determined by company policy. The load index means that, in addition to the total installation cost, a penalty is added by multiplying the cost of the most expensive cable by K. This reflects the maintenance and operational risks of including extremely expensive cables.

Takahashi wants to find a set of cables S that makes all bases connected while minimizing the load index. Find the minimum possible load index.

Note that it is guaranteed that there always exists a set of cables that makes all bases connected.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • N - 1 \leq M \leq 2 \times 10^5
  • 0 \leq K \leq 10^6
  • 1 \leq u_i, v_i \leq N
  • u_i \neq v_i
  • 1 \leq c_i \leq 10^6
  • All input values are integers.
  • There exists at least one set of cables that makes all bases connected.

Input

N M K
u_1 v_1 c_1
u_2 v_2 c_2
:
u_M v_M c_M
  • The 1st line contains the number of bases N, the number of candidate cables M, and the coefficient K, separated by spaces.
  • The next M lines provide information about each candidate cable.
  • The (1 + i)-th line contains the two bases u_i and v_i connected by candidate cable i, and its installation cost c_i, separated by spaces.

Output

Print the minimum load index in a single line.

Sample Input 1

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

Sample Output 1

22

Sample Input 2

3 3 0
1 2 7
2 3 2
1 3 5

Sample Output 2

7

Sample Input 3

8 12 5
1 2 4
1 3 8
2 3 3
2 4 7
3 5 6
4 5 2
4 6 9
5 6 5
5 7 10
6 8 4
7 8 1
3 8 12

Sample Output 3

55

Sample Input 4

12 20 100
1 2 15
2 3 18
3 4 14
4 5 16
5 6 20
6 7 13
7 8 17
8 9 19
9 10 12
10 11 21
11 12 11
1 6 50
2 7 45
3 8 40
4 9 35
5 10 30
6 11 25
7 12 22
1 12 100
3 10 28

Sample Output 4

2276

Sample Input 5

2 1 1000000
1 2 1000000

Sample Output 5

1000001000000