AT_jsc2021_h Shipping

AtCoder国家有从城市 $ {1} $ 到城市 $ {N} $ 的 $ {N} $ 个城市和从运河 $ {1} $ 到运河 $ {N} $ 的 $ {N} $ 条运河。 运河 $ {i} $ 将城市 $ {i} $ 和城市$ {A_i} $双向连接，通行费为$ {C_i} $日元。通过运河需要支付通行费，但只要支付一次，那条运河就可以在任何方向多次使用。 无论从哪个城市到哪个城市，都可以保证使用几条运河到达。 你被委托在AtCoder国家配送$ {M} $个行李。第i件行李必须从城市$ {X_i} $运到城市$ {Y_i} $。 搬运行李的手段除了运河以外没有，但是你自己不用运河也可以在城市之间自由移动。 配送所有 $ {M} $ 件行李时，请计算出支付通行费合计的最小值。 ### 题目补充 城市和运河的布局如下图所示。表示运河的线上写的数量表示运河的通行费 如下配送的话，需要支付的**通行费是10日元**。 第一件行李：使用运河**1和4**，按照城市**4→1→3**的顺序运输。 第二件行李：使用运河**3和1**，按照城市**2→3→1**的顺序运输。 

输入的以下形式由标准输入给出。 $ {N M A_1 C_1 A_2 C_2 A_3 C_3 ⋮ A_N C_N X_1 Y_1 X_2 Y_2 X_3 Y_3 ⋮ X_M Y_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 $ - 入力に含まれる値は全て整数である ### Sample Explanation 1 都市と運河の配置は以下の図のようになっています。 運河を表す線に書かれている数は、その運河の通行料を表します。 !\[図\](https://img.atcoder.jp/ghi/00d4990e6b1dd2b0c18ce27618430f91.png) 以下のように配送すると、払う必要のある通行料は $ 10 $ 円になります。 - $ 1 $ 個目の荷物 : 運河 $ 1,\ 4 $ を使って、都市 $ 4,\ 1,\ 3 $ の順に運ぶ - $ 2 $ 個目の荷物 : 運河 $ 3,\ 1 $ を使って、都市 $ 2,\ 3,\ 1 $ の順に運ぶ ### Sample Explanation 2 同じ都市の組を結ぶ運河が複数ある可能性があります。