配点 : $700$ 点

問題文

りんごさんは頂点に $1,2,...,N$ の番号がついた $N$ 個の頂点と $1,2,...,M$ の番号がついた $M$ 本の辺からなる無向グラフ $G$ を持っています。 辺 $i$ は頂点 $a_{i}$ と $b_{i}$ を双方向につなぐ長さ $w_i$ の辺です。

現在、りんごさんはこれらの $N$ 個の頂点を $1,2,...,K$ の番号がついた $K$ 種類の色で彩色している途中です。頂点 $i$ は色 $c_i$ で塗られています。ただし、$c_i = 0$ ならば頂点 $i$ にはまだ色が塗られていません。

りんごさんはまだ色が塗られていない全ての頂点を $K$ 種類の色のいずれかでそれぞれ塗ったのち、すぬけくんに $G$ をあげます。

すぬけくんは $G$ を使って頂点に $1,2,...,K$ の番号がついた $K$ 個の頂点と $M$ 本の辺からなる無向グラフ $G'$ を作ります。 はじめ、$G'$ には辺がありません。$i$ 番目の辺は以下のようにして追加されます。

• $G$ の辺 $i$ に着目したとき両端の頂点に塗られている色をそれぞれ $x,y$ とする
• 頂点 $x$ と $y$ を双方向につなぐ長さ $w_i$ の辺を $G'$ に追加する

$G'$ の最小全域木に含まれる辺の長さの総和としてありうる値は最小でいくつになりますか？りんごさんがどのように色を塗っても $G'$ が連結にならない場合は $-1$ を出力してください。

制約

• $1 \leq N,M \leq 10^{5}$
• $1 \leq K \leq N$
• $0 \leq c_i \leq K$
• $1 \leq a_i,b_i \leq N$
• $1 \leq w_i \leq 10^{9}$
• 与えられるグラフは単純とも連結とも限らない
• 与えられる入力は全て整数

部分点

• $100$ 点分のデータセットでは $N=K,c_i = i$ が成立する
• 別の $100$ 点分のデータセットでは $c_i \neq 0$ が成立する
• 別の $200$ 点分のデータセットでは $c_i = 0$ が成立する

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $K$

$c_1$ $c_2$ $...$ $c_{N}$

$a_1$ $b_1$ $w_1$

$:$

$a_M$ $b_M$ $w_M$

出力

答えを出力せよ。

4 3 3
1 0 1 2
1 2 10
2 3 20
2 4 50

60

頂点 $2$ に色 $3$ を塗ったときのみ、$G'$ が連結になります。

5 2 4
0 0 0 0 0
1 2 10
2 3 10

-1

どのようにりんごさんが色を塗っても、$2$ 本の辺で $4$ つの頂点が連結になるようにすることはできません。

9 12 9
1 2 3 4 5 6 7 8 9
6 9 9
8 9 6
6 7 85
9 5 545631016
2 1 321545
1 6 33562944
7 3 84946329
9 7 15926167
4 7 53386480
5 8 70476
4 6 4549
4 8 8

118901402

18 37 12
5 0 4 10 8 7 2 10 6 0 9 12 12 11 11 11 0 1
17 1 1
11 16 7575
11 15 9
10 10 289938980
5 10 17376
18 4 1866625
8 11 959154208
18 13 200
16 13 2
2 7 982223
12 12 9331
13 12 8861390
14 13 743
2 10 162440
2 4 981849
7 9 1
14 17 2800
2 7 7225452
3 7 85
5 17 4
2 13 1
10 3 45
1 15 973
14 7 56553306
16 17 70476
7 18 9
9 13 27911
18 14 7788322
11 11 8925
9 13 654295
2 10 9
10 1 545631016
3 4 5
17 12 1929
2 11 57
1 5 4
1 17 7807368

171