D - Network Construction Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は、N 台のサーバーを持つデータセンターのネットワーク管理者です。サーバーには 1 から N までの番号が付いています。

サーバー間を接続するために利用可能なケーブルが M 本あり、ケーブルにも 1 から M までの番号が付いています。i 番目のケーブル (1 \leq i \leq M) はサーバー U_i とサーバー V_i を双方向に結び、敷設コストが W_i です。各ケーブルは異なる2台のサーバーを結びます（すなわち U_i \neq V_i）。ただし、同じ2台のサーバーを結ぶケーブルが複数存在することもあります。

高橋君は、N 台のサーバーすべてが互いに通信できるよう、ケーブルをいくつか選んでネットワークを構築したいと考えています。選ぶケーブルの集合は全域木を成す必要があります。ここで全域木とは、N 台のサーバーすべてを頂点として含み、選んだケーブルによって全サーバーが連結であり、かつ閉路が存在しないようなグラフのことです（このとき選ばれるケーブルの本数はちょうど N-1 本になります）。

ただし、セキュリティ上の要件により、特定の K 本のケーブル（番号 E_1, E_2, \dots, E_K）は暗号化通信専用の回線として既に契約済みであり、必ずネットワークに含めなければなりません。

指定された K 本のケーブルをすべて含む全域木が存在する場合は、その全域木に含まれる N-1 本のケーブルの敷設コストの合計の最小値を出力してください。そのような全域木が存在しない場合は -1 を出力してください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 0 \leq K \leq N - 1
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i
  • 1 \leq W_i \leq 10^9
  • 1 \leq E_j \leq M（1 \leq j \leq K）
  • E_j はすべて異なる
  • 入力はすべて整数である

入力

N M K
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
E_1 E_2 \dots E_K
  • 1 行目には、サーバーの台数 N、利用可能なケーブルの本数 M、必ず含めなければならないケーブルの本数 K が、スペース区切りで与えられる。
  • 2 行目から M + 1 行目では、各ケーブルの情報が M 行で与えられる。
  • 1 + i 行目では、i 番目のケーブルがサーバー U_i とサーバー V_i を結び、敷設コストが W_i であることを表す。
  • K \geq 1 の場合、M + 2 行目には、必ずネットワークに含めなければならないケーブルの番号 E_1, E_2, \dots, E_K がスペース区切りで与えられる。K = 0 の場合、この行は存在しない。

出力

指定された K 本のケーブルをすべて含む全域木が存在する場合、その全域木に含まれる N-1 本のケーブルの敷設コストの合計の最小値を 1 行で出力せよ。存在しない場合は -1 を出力せよ。

入力例 1

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

出力例 1

8

入力例 2

3 3 2
1 2 1
1 2 2
2 3 3
1 2

出力例 2

-1

入力例 3

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

出力例 3

29

入力例 4

10 15 3
1 2 10
2 3 20
3 4 5
4 5 15
5 6 8
6 7 12
7 8 3
8 9 7
9 10 11
1 5 25
2 6 18
3 7 6
4 8 14
5 9 9
1 10 30
3 8 14

出力例 4

77

入力例 5

2 1 0
1 2 1000000000

出力例 5

1000000000

Score : 400 pts

Problem Statement

Takahashi is the network administrator of a data center with N servers. The servers are numbered from 1 to N.

There are M available cables for connecting servers, and the cables are also numbered from 1 to M. The i-th cable (1 \leq i \leq M) bidirectionally connects server U_i and server V_i, with an installation cost of W_i. Each cable connects two distinct servers (i.e., U_i \neq V_i). However, there may be multiple cables connecting the same pair of servers.

Takahashi wants to select some cables to build a network so that all N servers can communicate with each other. The set of selected cables must form a spanning tree. A spanning tree is a graph that includes all N servers as vertices, where all servers are connected by the selected cables, and no cycles exist (in this case, exactly N-1 cables are selected).

However, due to security requirements, a specific set of K cables (numbered E_1, E_2, \dots, E_K) have already been contracted as dedicated encrypted communication lines and must be included in the network.

If a spanning tree exists that contains all K specified cables, output the minimum total installation cost of the N-1 cables included in that spanning tree. If no such spanning tree exists, output -1.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 0 \leq K \leq N - 1
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i
  • 1 \leq W_i \leq 10^9
  • 1 \leq E_j \leq M (1 \leq j \leq K)
  • All E_j are distinct
  • All input values are integers

Input

N M K
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
E_1 E_2 \dots E_K
  • The first line contains the number of servers N, the number of available cables M, and the number of cables that must be included K, separated by spaces.
  • From the 2nd line to the (M + 1)-th line, the information of each cable is given over M lines.
  • The (1 + i)-th line indicates that the i-th cable connects server U_i and server V_i with an installation cost of W_i.
  • If K \geq 1, the (M + 2)-th line contains the cable numbers E_1, E_2, \dots, E_K that must be included in the network, separated by spaces. If K = 0, this line does not exist.

Output

If a spanning tree exists that contains all K specified cables, output in one line the minimum total installation cost of the N-1 cables included in that spanning tree. If no such spanning tree exists, output -1.

Sample Input 1

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

Sample Output 1

8

Sample Input 2

3 3 2
1 2 1
1 2 2
2 3 3
1 2

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

29

Sample Input 4

10 15 3
1 2 10
2 3 20
3 4 5
4 5 15
5 6 8
6 7 12
7 8 3
8 9 7
9 10 11
1 5 25
2 6 18
3 7 6
4 8 14
5 9 9
1 10 30
3 8 14

Sample Output 4

77

Sample Input 5

2 1 0
1 2 1000000000

Sample Output 5

1000000000