CF42E.Baldman and the military

Baldman is a warp master. He possesses a unique ability — creating wormholes! Given two positions in space, Baldman can make a wormhole which makes it possible to move between them in both directions. Unfortunately, such operation isn't free for Baldman: each created wormhole makes him lose plenty of hair from his head.

Because of such extraordinary abilities, Baldman has caught the military's attention. He has been charged with a special task. But first things first.

The military base consists of several underground objects, some of which are connected with bidirectional tunnels. There necessarily exists a path through the tunnel system between each pair of objects. Additionally, exactly two objects are connected with surface. For the purposes of security, a patrol inspects the tunnel system every day: he enters one of the objects which are connected with surface, walks the base passing each tunnel at least once and leaves through one of the objects connected with surface. He can enter and leave either through the same object, or through different objects. The military management noticed that the patrol visits some of the tunnels multiple times and decided to optimize the process. Now they are faced with a problem: a system of wormholes needs to be made to allow of a patrolling which passes each tunnel exactly once. At the same time a patrol is allowed to pass each wormhole any number of times.

This is where Baldman comes to operation: he is the one to plan and build the system of the wormholes. Unfortunately for him, because of strict confidentiality the military can't tell him the arrangement of tunnels. Instead, they insist that his system of portals solves the problem for any arrangement of tunnels which satisfies the given condition. Nevertheless, Baldman has some information: he knows which pairs of objects he can potentially connect and how much it would cost him (in hair). Moreover, tomorrow he will be told which objects (exactly two) are connected with surface. Of course, our hero decided not to waste any time and calculate the minimal cost of getting the job done for some pairs of objects (which he finds likely to be the ones connected with surface). Help Baldman!

巴尔德曼是一位空间跃迁大师。他拥有一种独特的能力——制造虫洞！给定空间中的两个位置，巴尔德曼可以创建一个双向虫洞，使得在这两个位置之间可以自由往返。不幸的是，这种操作对巴尔德曼而言并非免费：每创建一个虫洞，他都会从头上掉下大量头发。

正因拥有如此非凡的能力，巴尔德曼引起了军方的注意，并被委以一项特殊任务。但首先，让我们厘清背景。

军事基地由若干地下设施组成，其中部分设施通过双向隧道相互连通。整个隧道系统满足：任意两个设施之间必然存在一条路径（即图是连通的）。此外，恰好有两个设施与地表相连。出于安全考虑，巡逻员每日需对隧道系统进行例行检查：他从某一个与地表相连的设施进入基地，遍历整个基地（要求每条隧道至少经过一次），最后从某一个与地表相连的设施离开。他既可从同一设施进出，也可从不同设施进出。军方管理层注意到，巡逻员在执行任务时常会多次经过某些隧道，因此决定优化该流程。现在他们面临一个问题：需要构建一套虫洞系统，使得存在一种巡逻路线，能够恰好经过每条原始隧道一次（即形成一条欧拉路径）。同时，巡逻员可任意多次经过任意虫洞（即虫洞可重复使用）。

此时，巴尔德曼登场了：他将负责规划并建造这套虫洞系统。然而对他而言不幸的是，由于严格的保密要求，军方无法向他透露隧道的具体布局。取而代之的是，军方坚持要求：他所设计的虫洞系统必须能解决所有满足上述条件的隧道布局（即所有连通、且恰有两个端点与地表相连的无向图）。尽管如此，巴尔德曼仍掌握一些信息：他知道哪些设施对之间可能建立虫洞，以及相应所需付出的代价（以“掉发量”为单位）。此外，明天他将获知——哪两个设施（恰好两个）与地表相连。当然，我们的英雄决定不浪费一分一秒，提前计算出：对于某些他认为最有可能成为地表连接点的设施对，完成该任务所需的最小代价。请帮助巴尔德曼！

First line of the input contains a single natural number n (2 ≤ n ≤ 100000) — the number of objects on the military base. The second line — one number m (1 ≤ m ≤ 200000) — the number of the wormholes Baldman can make. The following m lines describe the wormholes: each line contains three integer numbers a, b, c (1 ≤ a, b ≤ n, 1 ≤ c ≤ 100000) — the numbers of objects which can be connected and the number of hair Baldman has to spend to make this wormhole.

The next line contains one natural number q (1 ≤ q ≤ 100000) — the number of queries. Finally, the last q lines contain a description of one query each — a pair of numbers of different objects a__i, b__i (1 ≤ a__i, b__i ≤ n, a__i ≠ b__i). There could be more than one wormhole between a pair of objects.

输入的第一行包含一个正整数 $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$）—— 表示可被连接的两个物体编号，以及 Baldman 制造该虫洞所需消耗的头发数量。

下一行包含一个正整数 $q$（$1 \leq q \leq 100000$）—— 查询的数目。
最后 $q$ 行每行描述一个查询——即一对不同的物体编号 $a_i,\,b_i$（$1 \leq a_i,b_i \leq n,\,a_i \neq b_i$）。
同一对物体之间可能存在多个虫洞。

Your program should output q lines, one for each query. The i-th line should contain a single integer number — the answer for i-th query: the minimum cost (in hair) of a system of wormholes allowing the optimal patrol for any system of tunnels (satisfying the given conditions) if a__i and b__i are the two objects connected with surface, or "-1" if such system of wormholes cannot be made.

你的程序应输出 $q$ 行，每行对应一个查询。第 $i$ 行应包含一个整数——即第 $i$ 个查询的答案：当 $a_i$ 和 $b_i$ 是通过地表相连的两个物体时，使得任意满足给定条件的隧道系统均能实现最优巡逻所需的虫洞系统的最小代价（单位：根头发）；若不存在满足要求的虫洞系统，则输出 -1。