P15877 [ICPC 2026 NAC] Cable Pruning

你正在帮助改造一个数据中心，以便为更多 GPU 腾出空间。多年来，数据中心中堆积了多余的网线，你被要求清理这些杂乱线缆，并尽可能多地回收未使用的线缆。 :::align{center}  样例输入 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 \ne 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 \ne b_j$），描述一个耦合对的服务器。在移除网线后，每个耦合对必须仍然存在一条路径保持连通。所有耦合对互不相同，$(a,b)$ 与 $(b,a)$ 视为相同，不会同时作为耦合对列出。

输出一个整数：为了使所有 $K$ 个耦合对之间保持连通，必须保留的网线的最小总长度（单位：英尺）。

翻译由 DeepSeek V3.2 完成