H - Shipping Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

AtCoder 国には、都市 1 から都市 N までの N 個の都市と運河 1 から運河 N までの N 本の運河があります。
運河 i は都市 i と都市 A_i を双方向に繋いでおり、通行料は C_i 円です。運河を通るには通行料を払う必要がありますが、1 度払えばその運河は任意の方向に何度でも使うことができます。
どの都市からどの都市へも、運河をいくつか使って辿り着けることが保証されます。

あなたは AtCoder 国で M 個の荷物配送を任されました。i 個目の荷物は都市 X_i から都市 Y_i へと運ばなければなりません。
荷物を運ぶ手段は運河以外にありませんが、あなた自身は運河を使わずとも都市間を自由に移動することができます。

M 個の荷物全てを配送するとき、払う通行料の合計として考えられる最小値を求めてください。

制約

  • 3 \le N \le 2 \times 10^5
  • 1 \le M \le 2 \times 10^5
  • 1 \le A_i \le N
  • A_i \neq i
  • 1 \le C_i \le 10^9
  • どの都市からどの都市へも、運河をいくつか使って辿り着ける
  • 1 \le X_i \le N
  • 1 \le Y_i \le N
  • X_i \neq Y_i
  • 入力に含まれる値は全て整数である

入力

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

N M
A_1 C_1
A_2 C_2
A_3 C_3
\hspace{13pt} \vdots
A_N C_N
X_1 Y_1
X_2 Y_2
X_3 Y_3
\hspace{13pt} \vdots
X_M Y_M

出力

払う通行料の合計として考えられる最小値 [円] を出力せよ。

入力例 1

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

出力例 1

10

都市と運河の配置は以下の図のようになっています。
運河を表す線に書かれている数は、その運河の通行料を表します。
図

以下のように配送すると、払う必要のある通行料は 10 円になります。

  • 1 個目の荷物 : 運河 1, 4 を使って、都市 4, 1, 3 の順に運ぶ
  • 2 個目の荷物 : 運河 3, 1 を使って、都市 2, 3, 1 の順に運ぶ

入力例 2

5 2
2 2
5 5
5 7
2 4
3 10
3 5
4 1

出力例 2

13

同じ都市の組を結ぶ運河が複数ある可能性があります。

入力例 3

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

出力例 3

26

Score : 600 points

Problem Statement

In the Republic of AtCoder, there are N cities called City 1 through City N and N canals called Canal 1 through Canal N.
Canal i connects City i and City A_i bidirectionally, and you have to pay the toll of C_i yen to go through it, but after paying the toll once, you can use it any number of times in any direction.
It is guaranteed that you can reach from any city to any city using some canals.

You are asked to deliver M cargoes in this country. The i-th cargo should be delivered from City X_i to City Y_i.
There is no way other than using the canals to deliver the cargoes, but you yourself can travel between the cities freely without using the canals.

Find the minimum total toll you have to pay to deliver all M cargoes.

Constraints

  • 3 \le N \le 2 \times 10^5
  • 1 \le M \le 2 \times 10^5
  • 1 \le A_i \le N
  • A_i \neq i
  • 1 \le C_i \le 10^9
  • It is possible to reach from any city to any city by using some canals.
  • 1 \le X_i \le N
  • 1 \le Y_i \le N
  • X_i \neq Y_i
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 C_1
A_2 C_2
A_3 C_3
\hspace{13pt} \vdots
A_N C_N
X_1 Y_1
X_2 Y_2
X_3 Y_3
\hspace{13pt} \vdots
X_M Y_M

Output

Print the minimum total toll you have to pay, as an integer.

Sample Input 1

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

Sample Output 1

10

The figure below shows the cities and canals in this country, where numbers along the lines representing canals represent the tolls:
Figure

You can deliver the cargoes as follows to make the total toll 10 yen:

  • The 1-st cargo: use Canal 1, 4 to deliver it on the route: City 4, 1, 3.
  • The 2-nd cargo: use Canal 3, 1 to deliver it on this route: City 2, 3, 1.

Sample Input 2

5 2
2 2
5 5
5 7
2 4
3 10
3 5
4 1

Sample Output 2

13

Multiple canals may connect the same pair of cities.

Sample Input 3

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

Sample Output 3

26