你正在协助改造一个数据中心，以便为更多的 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