009 - 魔法の糸

問題

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

頂点数 N ，辺数 M の連結な無向グラフ G が与えられる．それぞれの頂点には 0 , ... , N−1 の番号が対応している．辺には整数の長さが付いている． G 上の頂点を分割するグループについて考える． はじめは，頂点 0 , 1 , ... , N−1はそれぞれ自身のみを含むグループに属しているとする．
2 つのグループを合併して新たなグループとする「合併クエリ」が Q 回与えられる．それぞれの合併クエリに対して，合併されてできた新たなグループに含まれる頂点のみを連結にするために必要な辺の集合で，その長さの和が最小となるものを求め，その和を出力せよ．

入力

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

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

出力

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

制約

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

• 2 ≦ N ≦ 2000
• 1 ≦ M ≦ 200000
• 0 ≦ u_i , v_i ≦ N
• 1 ≦ w_i ≦ 100000
• 1 ≦ Q ≦ N
• 0 ≦ p_i , q_i ≦ N
• 与えられるグラフは連結であり，多重辺やループを含まない
• 既に同じグループに属している2点がクエリとして与えられることはない

---

入出力例

入力例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