#215576. [JOI 2026 SemiFinal] 川下り / River Rafting

JOI 国には 個の街があり，街には から までの番号が付けられている．これらの街の間には 本の道があり， から までの番号が付けられている．道 () は街 () と街 とを相互に結んでいる．街 からどの街へも何本かの道を通って移動できることが保証されている．

また，JOI 国には道に並行する川が 本あり，川には から までの番号が付けられている．川 () は道 と並行しており，街 から街 の向きに流れている．

個の街にはそれぞれ つずつランプが置かれている．各ランプには強さが定められている．街 () にあるランプの強さが であるとき，その街から 本未満の道を通って到達できる街はこのランプによって照らされている．最初の時点では，ランプの強さはすべて であり，どの街も照らされていない．

あなたは川下りを 回以上好きな回数行うことができる．川下りは街 にいる状態から始めて，まず街 にあるランプの強さを 増やす．そして，以下の操作を順に繰り返す．

1. 川下りを終了するか決める．ただし今いる街から流れる川が存在しないときは必ず終了する．
2. 川下りを続ける場合，今いる街から流れる川を つ選び，その川の流れに沿って移動する．移動した先の街のランプの強さを 増やす．

川下りを街 で終了した場合，この川下りにかかるコストは である．あなたは，川下りを 回以上好きな回数行うことで，すべての街がいずれかのランプによって照らされるようにしたい．その上で，川下りにかかるコストの合計を最小化する必要がある．

道とコストの情報が与えられたとき，すべての街がいずれかのランプによって照らされるようにするための川下りにかかるコストの合計の最小値を求めるプログラムを作成せよ．

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

標準出力に，すべての街がいずれかのランプによって照らされるようにするための川下りにかかるコストの合計の最小値を 行で出力せよ．

样例输入 1

5
1 2 2 4
10 4 8 9 5

样例输出 1

9

样例输入 2

9
1 1 1 2 5 5 5 3
100 70 80 90 60 30 40 50 30

样例输出 2

90

Sample Explanation 1

1 回目の川下りでは川 を選択し，街 で川下りを終了する．このとき街 にあるランプの強さが 増え，コストは である．2 回目の川下りでは川 を選択し，街 で川下りを終了する．このとき街 にあるランプの強さが 増え，コストは である．

操作の後，街 にあるランプの強さは ，街 にあるランプの強さは ，街 にあるランプの強さは となる．街 は街 にある強さ のランプによって，街 は街 にある強さ のランプによって照らされる．したがって，これらの操作によりすべての街はいずれかのランプによって照らされる．このときコストの合計は である． 未満のコストで条件を満たすことはできないため， を出力する．

この入力例は小課題 1,2,5,6 の制約を満たす．

Sample Explanation 2

川 を通って街 で終了する川下りを 回，川 を通って街 で終了する川下りを 回行う．操作の後，街 にあるランプの強さは ，街 にあるランプの強さは ，街 にあるランプの強さは ，街 にあるランプの強さは となる．これらの操作によりすべての街はいずれかのランプによって照らされる．このときコストの合計は である． 未満のコストで条件を満たすことはできないため， を出力する．

この入力例は小課題 2,6 の制約を満たす．

制約

• ．
• ()．
• ()．
• 入力される値はすべて整数である．

小課題

1. 点．
2. 点．
3. 点 ()．
4. 点 ()．
5. 点すべての () に対して， となる () は 個以下．
6. 点追加の制約はない．