分数: 600 点
问题陈述
在AtCoder共和国,有 N 城市称为 City 1 穿越城市 N 和 N 称为 Canal 的运河 1 通过运河 N.
运河 i 连接城市 i 和城市 A_i 双向,您必须支付 C_i 日元即可通过,但缴纳一次通行费后,可以在任何方向使用任意次数。
保证您可以使用一些运河从任何城市到达任何城市。
您被要求交付 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-st 货物:使用运河 1, 4 交付路线: 城市 4, 1, 3.
- 的 2-nd 货物:使用运河 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