问题

背景

鳗鱼王国长期使用信函鳗鱼作为通信手段，但近年来发明了一种可以瞬间传达声音的魔法线，因此国王决定用这种魔法线连接城市之间，从而完善通信网。由于魔法线的生产需要时间，最初计划在交情很深的城镇之间建立一个小组，只在其中进行通信，慢慢地将小组合并，在广泛的范围内进行通信。用魔法线连接某一小组中包含的城镇需要多长的魔法线呢？

挑战

顶点数 $N$，边数 $M$ 的连接的无向曲线$G$。每个顶点都有 $0$，$N-1$ 的编号对应。边上有整数的长度。考虑分割G上顶点的组。首先是顶点 $0,1,N-1$（14:04修正）分别属于只包含自身的组。

将两个组合并作为新组的“合并查询”被给予 $Q$ 次。对于各个合并查询，仅将合并后的新组中包含的顶点（13:25追记）作为连接所需的边的集合，求其长度之和为最小的，输出其和。

输入

输入以以下形式给出。

$N M$

$u_1 v_1 w_1$

...

$u_M v_M w_M$

$Q$

$p_1 q_1$

...

$p_Q q_Q$

$N$代表图的顶点数， $M$ 代表边数。接下来的 $M$ 行表示边的信息，每行包含三个整数 $u_i,v_i$和 $w_i$，表示顶点 $u_i$ 和顶点 $v_i$之间存在一条长度为　$w_i$ 的边。$Q$ 表示要执行的合并查询的数量。接下来的 $Q$ 行表示合并查询，每行包含两个整数 $p_i$ 和$q_i$，表示将包含顶点 $p_i$ 的组与包含顶点 $q_i$ 的组进行合并。

约束条件如下：

$2≤N≤2,000$

$1≤M≤200,000$

$0≤u_i, v_i<N$

$1≤w_i≤100,000$

$1≤Q<N$

$0≤p_i, q_i<N$

给定的图是连通的，不包含重复边和环 不会出现已经属于同一组的两个顶点作为查询的情况

输出： 输出由 $Q$ 行组成。第 $i$ 行应输出在第$i$ 个合并查询中，使得合并后的组成为一个连通图所需的边的长度之和的最小值。如果不存在这样的边集合，则输出IMPOSSIBLE。