The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 2 – Reconstruction Project

復興事業 (Reconstruction Project)

JOI 町はかつて栄えた工業地域であり，物資の運搬のために数多くの駅や線路が建設された．現在は衰退してしまったが，使われなくなった駅や線路は今もなお残されたままである．

JOI 町には N 個の駅が残されており，1 から N までの番号が付けられている．また M 本の線路が残されており，i 本目 (1 ≦ i ≦ M) の線路は駅 Ai と 駅 Bi を双方向に結び，そのレール幅は Wi である．どの駅からどの駅へもいくつかの線路を通って到達できる．

JOI 町の町長であるあなたは，この残された駅と線路を用いて鉄道会社を誘致し，JOI 町を鉄道の町として復興させることにした．するとこの復興事業に Q 社の鉄道会社が名乗りを挙げた．しかし鉄道会社ごとに，保有する列車に対応するレール幅が決まっているため，線路のレール幅を列車に合わせるための工事が必要であることが分かった．

j 番目 (1 ≦ j ≦ Q) の鉄道会社の列車に対応するレール幅は X j である． j 番目の鉄道会社を誘致するには次の条件を満たす必要がある．
条件 どの駅からどの駅へも，レール幅が X j である線路のみを通って到達できる．
この条件を満たすようにするために，あなたは次の工事を好きなだけ行える．
工事 線路を 1 つ選び，その線路のレール幅を 1 だけ増やすまたは減らす．これにはコストが 1 だけかかる．ただし，レール幅が 1 である線路のレール幅をさらに減らすことはできない．
あなたは誘致する鉄道会社を決めるために，各鉄道会社を誘致するのにそれぞれ最小でいくらコストがかかるのかを見積もりたい．
駅と線路，鉄道会社の情報が与えられたとき，各鉄道会社を誘致するためにかかるコストの最小値を求めるプログラムを作成せよ．

復興事業– 1 / 5

The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 2 – Reconstruction Project

入力
入力は以下の形式で標準入力から与えられる．入力される値はすべて整数である．

NM
A1 B1 W1A2 B2 W2..
.
A M BM W M
Q
X1X2..
.
XQ

出力
標準出力に Q 行で出力せよ． j 行目 (1 ≦ j ≦ Q) には j 番目の鉄道会社を誘致するためにかかるコストの最小値を出力せよ．

制約• 2 ≦ N ≦ 500．
• N − 1 ≦ M ≦ 100 000．
• 1 ≦ Q ≦ 1 000 000．
• 1 ≦ Ai < Bi ≦ N (1 ≦ i ≦ M)．
• 1 ≦ Wi ≦ 1 000 000 000 (= 109 ) (1 ≦ i ≦ M)．
• (Ai , Bi , Wi ) , (A j , B j , W j ) (1 ≦ i < j ≦ M)
• どの駅からどの駅へもいくつかの線路を通って到達できる．
• 1 ≦ X j ≦ 1 000 000 000 (= 109 ) (1 ≦ j ≦ Q)．
• X j < X j+1 (1 ≦ j ≦ Q − 1)．

復興事業– 2 / 5

The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 2 – Reconstruction Project

小課題
1. (9 点) M ≦ 16，Q ≦ 10．
2. (11 点) Q ≦ 10．
3. (18 点) Bi = Ai + 1 (1 ≦ i ≦ M)．
4. (23 点) M ≦ 1 000．
5. (28 点) Q ≦ 20 000．
6. (11 点) 追加の制約はない．

入出力例
入力例 1出力例 15 108

1 2 821 3 135

1 4 5101 5 119

1 5 3212 3 7
2 4 153 4 6
3 5 6
4 5 26368101317例えば 1 番目の鉄道会社を誘致するとき，以下のように工事を行うとコストが 8 かかる．

1. 6 本目の線路のレール幅を 4 だけ減らす．これにはコストが 4 だけかかる．

復興事業– 3 / 5

The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)Contest 2 – Reconstruction Project
2. 9 本目の線路のレール幅を 3 だけ減らす．これにはコストが 3 だけかかる．
3. 10 本目の線路のレール幅を 1 だけ増やす．これにはコストが 1 だけかかる．
コスト 8 未満で 1 番目の鉄道会社を誘致することはできないので，1 行目には 8 を出力する．
この入力例は小課題 1, 2, 4, 5, 6 の制約を満たす．
入力例 2

出力例 23 4

11 2 1

11 2 422 3 202 3 441234
この入力例はすべての小課題の制約を満たす．

復興事業– 4 / 5

The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying TrialMarch 20–23, 2022 (Komaba, Tokyo)
Contest 2 – Reconstruction Project
入力例 3出力例 310 201121073688

6 7 914727791

761832468

1 8 771674531

1026806785

3 5 632918108

1316097872

5 9 329296846

1321500065

1 7 237501112

1445238392

4 9 303328173

1637513141

2 6 216298255

1621778548

2 10 504024991

1733953031

3 8 158236886

1738749711

1 10 10176179
8 9 918271145
3 6 217165898
3 6 624543444
4 9 70147274
8 9 976983490
6 9 210108505
2 9 972711062
1 10 564567289
3 7 411395464
4 7 952470985
10115721165
198969744
356664401
429802521
513343279
610443927
741016686
786597783
898772266
903568946
この入力例は小課題 2, 4, 5, 6 の制約を満たす．

復興事業– 5 / 5