您正在協助改造資料中心，以便為更多的 GPU 騰出空間。多年來，資料中心堆積了許多多餘的網路纜線，您被要求清理這些雜亂的纜線，並儘可能回收未使用的纜線。

圖 C.1：範例輸入 1 的示意圖。屬於同一配對的伺服器顏色相同。虛線表示要移除的纜線。

資料中心有 $N$ 台伺服器和 $N$ 條連接伺服器的網路纜線。每條纜線都有其長度（以英尺為單位）。流量在網路纜線中雙向流動，且資料中心最初是連通的：對於每一對伺服器 $(u, v)$，都存在一條由網路纜線組成的路徑從 $u$ 到 $v$（可能經過中間伺服器）。您審核了資料中心的網路流量，發現只有 $K$ 對伺服器配對需要互相通訊。（請注意，有些伺服器可能不屬於任何配對，也可能屬於兩個或多個配對。）

您現在需要從資料中心移除儘可能多的纜線總長度，同時保持所有配對的伺服器彼此連通：對於每一對這樣的伺服器 $(a, b)$，必須存在一條從 $a$ 到 $b$ 的路徑，且該路徑必須通過您保留的原始網路纜線。

請找出為了滿足此限制而必須保留的纜線總長度的最小值。

輸入格式

第一行包含兩個以空格分隔的整數 $N$ ($3 \le N \le 10^5$) 和 $K$ ($1 \le K \le 10^5$)，分別代表資料中心內的伺服器數量以及您發現的伺服器配對數量。

接下來的 $N$ 行描述資料中心內原有的網路纜線。每行包含三個以空格分隔的整數 $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$ 英尺。每對伺服器之間最多只有一條網路纜線，且伺服器與纜線組成的圖是連通的。

接下來的 $K$ 行，每行包含兩個以空格分隔的整數 $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