データセンターのGPU増設に向けた改装を手伝うことになりました。長年にわたり、データセンターには不要なネットワークケーブルが散乱しており、この混乱を整理し、可能な限り未使用のケーブルを回収するように依頼されました。

図 C.1: サンプル入力 1 の図。同じ色のサーバーは結合ペアである。取り除くべきケーブルは破線で示されている。

データセンターには $N$ 台のサーバーと、サーバー間を接続する $N$ 本のネットワークケーブルがあります。各ケーブルにはフィート単位の長さがあります。トラフィックはネットワークケーブルを通じて双方向に流れ、データセンターは初期状態で接続されています。つまり、すべてのサーバーのペア $(u, v)$ について、$u$ から $v$ へのネットワークケーブルの経路（中間サーバーを経由する場合もある）が存在します。データセンターのネットワークトラフィックを監査した結果、通信が必要なサーバーのペアは $K$ 組の結合ペアのみであることがわかりました。（一部のサーバーはどの結合ペアにも含まれていない場合や、2つ以上の結合ペアに含まれている場合があることに注意してください。）

すべての結合ペアが互いに接続された状態を維持しつつ、データセンターから可能な限り多くの合計長さのケーブルを取り除く必要があります。つまり、そのような各サーバーのペア $(a, b)$ について、残した元のネットワークケーブルを経由して $a$ から $b$ への経路が存在しなければなりません。

この制約を満たすために残さなければならないケーブルの合計長さの最小値を求めてください。

入力

入力の最初の行には、2つのスペース区切りの整数 $N$ ($3 \le N \le 10^5$) と $K$ ($1 \le K \le 10^5$) が含まれており、それぞれデータセンター内のサーバーの数と、発見されたサーバーの結合ペアの数を示します。

続く $N$ 行は、データセンターに元々あったネットワークケーブルを記述しています。各行には3つのスペース区切りの整数 $u_i, v_i$ ($1 \le u_i, v_i \le N, u_i \neq v_i$) と $w_i$ ($1 \le w_i \le 10^9$) が含まれており、サーバー $u_i$ とサーバー $v_i$ を接続する長さ $w_i$ フィートのケーブルがあることを示しています。サーバーのペアを接続するネットワークケーブルは最大で1本であり、サーバーとケーブルのグラフは接続されています。

続く $K$ 行の各行には、2つのスペース区切りの整数 $a_j$ と $b_j$ ($1 \le a_j, b_j \le N, a_j \neq b_j$) が含まれており、結合されたサーバーのペアを記述しています。ケーブルを取り除いた後も、各結合ペアは経路によって接続されたままでなければなりません。すべての結合ペアは一意であり、$(a, b)$ と $(b, a)$ は同じものとみなされ、両方が結合ペアとしてリストされることはありません。

出力

すべての $K$ 組の結合サーバーペアが互いに接続された状態を維持するために残さなければならないネットワークケーブルの合計長さ（フィート単位）の最小値を、単一の整数で出力してください。

入出力例

入力 1

8 3
5 3 5
1 7 20
3 8 8
7 5 15
5 2 12
1 6 9
5 1 10
7 4 7
3 4
8 2
1 7

出力 1

57

入力 2

5 1
1 3 3
4 2 4
3 4 2
5 2 2
4 1 6
2 1

出力 2

9