問題文に修正があります (14:04)

問題に関して追記があります (13:25)

問題

背景

うなぎ王国では長らく通信の手段として伝書うなぎが使われてきたが，近年一瞬で声を伝達することができる魔法の糸が発明された．そこで王様は，この魔法の糸で町の間を繋ぐことによって通信網を整備することにした．魔法の糸の生産には時間がかかるので，はじめは親交の深い町同士でグループを作りその中でのみ通信できるようにし，徐々にグループを合併して広い範囲で通信できるようにするという計画を立てた．あるグループに含まれる町同士を魔法の糸で繋ぐにはどれだけの長さの魔法の糸が必要だろうか．

課題

頂点数 N ，辺数 M の連結な無向グラフ G が与えられる．それぞれの頂点には 0 ,..., N-1 の番号が対応している．辺には整数の長さが付いている． G 上の頂点を分割するグループについて考える． はじめは，頂点 0 , 1 ,..., N-1(14:04修正) はそれぞれ自身のみを含むグループに属しているとする．

2 つのグループを合併して新たなグループとする「合併クエリ」が Q 回与えられる．それぞれの合併クエリに対して，合併されてできた新たなグループに含まれる頂点のみ（13:25追記）を連結にするために必要な辺の集合で，その長さの和が最小となるものを求め，その和を出力せよ．

配点

200

入力

入力は以下の形式で与えられる．

N M
u1 v1 w1
...
uM vM wM
Q
p1 q1
...
pQ qQ

N , M はそれぞれグラフの頂点数，辺数を表す．続く M 行は辺の情報を表す．u_i, v_i, w_i は 頂点u_i と 頂点v_iの間に長さ w_i の辺があることを表す．Qは合併クエリの数を表す．続く Q 行は，頂点 p_i を含むグループと頂点 q_i を含むグループの合併クエリを表す．

制約

入力中の各変数は以下の制約を満たす．

• 2 \leq N \leq 2,000
• 1 \leq M \leq 200,000 (=2\times 10⁵)
• 0 \leq u_i, v_i \lt N
• 1 \leq w_i \leq 100,000 (=10⁵)
• 1 \leq Q \lt N
• 0 \leq p_i, q_i \lt N
• 与えられるグラフは連結であり，多重辺やループを含まない
• 既に同じグループに属している2点がクエリとして与えられることはない

出力

出力は Q 行からなる． i 行目には，i 番目の合併クエリで合併されたグループを連結にするために必要な辺の長さの和の最小値を出力せよ．ただし，そのような辺の集合が存在しない場合は "IMPOSSIBLE" と出力せよ．

入力例1

3 3
0 1 2
0 2 1
1 2 1
2
0 1
1 2

入力例1に対する出力例

2
2

はじめは，それぞれの頂点は自身のみを含むグループに属している．最初のクエリで頂点 0 を含むグループと頂点 1 を含むグループが合併される．合併したグループは頂点 0 と頂点 1 からなる．この 2 つの頂点を連結にするためには 1 本辺が必要であり，そのような辺の長さの最小値は 2 である．次のクエリで頂点 1 の属するグループと頂点 2 の属するグループが合併され，すべての頂点が 1 つのグループになる．このグループを連結にするような辺の長さの和の最小値は 2である．

入力例2

5 7
0 1 3
0 4 3
1 2 2
1 3 1
1 4 4
2 3 3
3 4 3
4
0 1
2 4
1 3
3 4

入力例2に対する出力例

3
IMPOSSIBLE
4
9