CF42E Baldman and the military

Baldman 是一位“虫洞大师”。他拥有一个独特的能力 —— 创建虫洞！给定空间中的两个位置，Baldman 可以在它们之间制造一个虫洞，使得可以在这两个位置之间双向通行。不幸的是，每创建一个虫洞，他就会失去大量的头发。 因为这种非凡的能力，Baldman 引起了军方的注意。他被赋予了一项特殊的任务。但在此之前，让我们先了解背景。 这个军事基地由若干个地下目标组成，其中一些目标之间有双向隧道相连。保证任意两个目标之间至少存在一条隧道路径。另外，恰有两个目标与地面相连。为了安全起见，巡逻兵每天要检查隧道系统：他从**某个**与地面相连的目标进入，经过基地，每条隧道至少走一次，然后从与地面相连的**某个**目标离开。**他可以从同一个目标进出，也可以从不同目标进出**。军事管理层注意到，巡逻兵有时会多次经过一些隧道，因此决定优化巡逻流程。现在他们面临一个问题：需要建立一套虫洞系统，以便每条隧道**仅被经过一次**进行巡逻。同时，巡逻允许对每个虫洞不限次数通过。 这就是 Baldman 登场的时候：他要负责规划并建立虫洞系统。不幸的是，因高度机密，军方无法告诉他隧道的实际布局。相反，他们坚持让虫洞系统适用于所有满足上述条件的隧道布局。不过，Baldman 还是知道一些信息：他知道可以潜在连接哪些目标对，以及每个虫洞需要耗费多少头发。此外，明天他会被告知哪两个目标与地面相连。当然，他决定未雨绸缪，先对一些可能成为“与地面相连目标”的目标对，计算实现任务的最低代价。请你帮助 Baldman！

输入的第一行包含一个正整数 $n$（$2 \leq n \leq 100000$），表示军事基地中的目标数量。 第二行包含一个整数 $m$（$1 \leq m \leq 200000$），表示 Baldman 能制造的虫洞数量。 接下来的 $m$ 行，每行三个整数 $a, b, c$（$1 \leq a, b \leq n, 1 \leq c \leq 100000$），表示可以在 $a$ 和 $b$ 之间制造一个虫洞，所需耗费为 $c$ 根头发。 接下来一行一个正整数 $q$（$1 \leq q \leq 100000$），表示询问的数量。 最后 $q$ 行，每行两个整数 $a_i, b_i$（$1 \leq a_i, b_i \leq n, a_i \neq b_i$），表示一次询问：这两个目标被选为与地面相连的目标。 一个目标对之间可以有多个虫洞。

输出 $q$ 行，每行一个整数，其中第 $i$ 行为第 $i$ 个询问的答案：为了使巡逻路线能够最优、并适用于所有满足条件的隧道系统，若 $a_i$ 和 $b_i$ 为与地面相连的两点时，建立虫洞系统的最小耗发代价。如无法建成满足条件的虫洞系统，输出 $-1$。

由 ChatGPT 5 翻译