WW

Time Limit : 8 sec, Memory Limit : 262144 KB

Problem L: WW

Problem

19XX年、nつの国で連合国軍が結成された。連合国軍に属する各国では、敵軍の侵略から自国を守るために国内に1つ以上の拠点を作り、周囲を警戒している。図1は連合国の例を示し、長方形が各国を、その中にある円がその国の拠点を表す。


図1
図1

敵軍が侵略してきた場合、それを一番最初に発見した拠点からその情報を連合国軍に属する他国または自国の拠点に発信することになっている。 情報を他の拠点に伝えるには正の整数のコストがかかる。

また、各国では自国の拠点のうち、連合国軍翻訳通信部(ATIS : Allied Translator and Interpreter Section)に属する兵士が配属されている拠点をちょうど1つだけ持っている。 この兵士だけが連合国軍に属する全ての国の言語を話すことができ、その他の兵士は自分の国の言語しか話せない。 その為、情報を受け取った拠点が他国に情報を伝えようとした際にその拠点がATISに属する兵士をもたない場合、そこから自国のATISに属する兵士をもつ拠点に情報を伝え他国に情報を発信してもらう必要がある。

国毎で各拠点に0から順に[その国がもつ拠点の数-1]までの番号が割り振られており、0番目の拠点にATISに属する兵士がいる。 つまり、他国の拠点に情報を伝達できるのは0番目の拠点だけであり、その他の拠点から他国へは通信できない。 また、その国の0番目の拠点に情報が伝わればその国全体に情報が伝わったものとする。

様々な理由から、全ての拠点の間で通信ができるとは限らない。 ある拠点から別の拠点に情報を伝える事ができたとしても、その逆が成り立つとは限らない。 また、ある拠点から別の拠点に情報を伝えた際のコストとその逆でかかるコストが同じとも限らない。

これらのことを踏まえて、ある拠点が敵軍を発見した際に、連合国軍全体に情報が行き渡るコストの総和が最も少ない伝達方法を知りたい。 連合国軍に属する全ての国の0番目の拠点に対して最初に敵軍を見つけた拠点から情報が伝達された時、連合国軍全体に情報が行き渡ったものとする。

敵軍を発見した拠点が質問として与えられるので、最も少ないコストでその情報が連合国軍全体に行き渡る伝達方法とそのコストを出力せよ。

例えば、以下のケースについて考える ( Sample Input 4、1つめの質問 )

国neepalの1番目の拠点が敵軍を発見したとする。 この場合、1番目の拠点から他国へは通信できないため、まず自国の0番目の拠点へ情報を伝える。

次に、0番目の拠点から国luxenbourg,nowayに情報を伝える。 neepalからluxenbourgの0番目の拠点へ直接通信することはできるが、3番目の拠点に情報を伝え、そこから0番目の拠点へ伝えたほうがコストが少なく済む。 この場合、全ての国の0番目の国へ情報を伝えるためにかかる最小のコストは12となる。 コストが12で済む伝達方法は複数存在するが、そのうちのどれか一つを答えとして出力すれば良い。

以下の図2の赤い矢印はその答えのうちの1つである。



図2

Input

n
countryname0 m0 
countryname1 m1countrynamen-1 mn-1
e
c10 v10 c20 v20 cost0
c11 v11 c21 v21 cost1c1e-1 v1e-1 c2e-1 v2e-1 coste-1
q 
c30 v30 
c31 v31c3q-1 v3q-1

  • nは連合国軍に属する国の数を表す
  • countrynameiは連合国軍に属するi番目の国名を,mii番目の国の拠点の数を表す
  • eは通信可能な拠点のペアの数を表す
  • 続くe行には国c1iの拠点v1iから国c2iの拠点v2iに情報を伝えるのにかかるコストcostiが与えられる
  • qは質問の数を表す
  • 続くq行には敵軍を発見した国の名前c3iとその拠点v3iが与えられる
  • c1i,c2i,c3iは連合国軍に属する国のいずれかである
  • v1i,v2i,v3iはその国の拠点の数以上である事は無い

Constraints

  • 1 ≤ n ≤ 26
  • 1 ≤ mi ≤ 100
  • 0 ≤ e ≤ 322400
  • 0 ≤ costi ≤ 100
  • 1 ≤ q ≤ 10
  • countryname は小文字のアルファベット ‘a’ から’z’までで構成される長さ1以上20以下の文字列である
  • 同じ名前の国が2つ以上与えられる事はない
  • 通信可能な拠点のペアのc1ic2iが同じ時、v1iv2iは異なる
  • 通信可能な拠点のペアのc1ic2iが異なる時、v1iは必ず0である

Output

各質問に対して以下の形式で答えを出力する。

各質問に対する答えの最後の行には、5つの '-’ からなる"-----” ( “ は除く ) という1行を出力すること。

答えが存在する場合

1行目に質問で与えられた国の拠点から連合国軍全体に情報が行き渡るために必要なコストの最小値を出力する。

2行目以降にはその時の伝達方法を出力する。 伝達方法は以下の形式で表現される。

c40 v40 c50 v50 
c41 v41 c51 v51 
...

c4iの拠点v4iから国c5iの拠点v5iに情報を伝えたことを表す。

以下の事に気をつける事。

  • 通信が行われた順番通りに出力する必要はない
  • コストの総和が最小となる伝達方法が1つ以上存在する場合、そのうちのいずれか1つを出力すれば良い
  • 同じ通信可能なペアを2回以上出力してはいけない
  • c4i,c5iは入力で与えられた国のいずれかでなければならない
  • v4i,v5iはその国の拠点の数未満でなければならない

答えが存在しない場合

1行に ”Impossible” ( “ は除く ) と出力すること。

Sample Input 1

3
frence 1
usi 1
powland 1
2
usi 0 frence 0 10
frence 0 powland 0 10
2
usi 0
powland 0

Sample Output 1

20
usi 0 frence 0
frence 0 powland 0
-----
Impossible
-----

Sample Input 2

2
usso 2
caneda 2
4
usso 1 usso 0 1
usso 0 caneda 0 10
usso 0 caneda 1 2
caneda 1 caneda 0 2
1
usso 1

Sample Output 2

5
usso 1 usso 0
usso 0 caneda 1
caneda 1 caneda 0
-----

Sample Input 3

3
chinax 1
ok 1
austraria 2
6
chinax 0 austraria 0 5
austraria 0 chinax 0 5
austraria 1 austraria 0 1
ok 0 austraria 0 5
austraria 0 ok 0 5
ok 0 austraria 1 1
2
chinax 0
ok 0

Sample Output 3

10
chinax 0 austraria 0
austraria 0 ok 0
-----
7
ok 0 austraria 1
austraria 1 austraria 0
austraria 0 chinax 0
-----

Sample Input 4

3
neepal 2
luxenbourg 4
noway 2
12
neepal 1 neepal 0 2
neepal 0 noway 1 2
neepal 0 luxenbourg 0 10
neepal 0 luxenbourg 3 2
luxenbourg 3 luxenbourg 1 2
luxenbourg 3 luxenbourg 2 2
luxenbourg 1 luxenbourg 0 2
luxenbourg 2 luxenbourg 0 2
noway 1 noway 0 2
noway 0 neepal 0 2
noway 0 luxenbourg 3 2
noway 0 luxenbourg 0 10
3
neepal 1
luxenbourg 3
noway 1

Sample Output 4

12
neepal 1 neepal 0
neepal 0 luxenbourg 3
luxenbourg 3 luxenbourg 2
luxenbourg 2 luxenbourg 0
neepal 0 noway 1
noway 1 noway 0
-----
Impossible
-----
10
noway 1 noway 0
neepal 0 luxenbourg 3
luxenbourg 3 luxenbourg 2
luxenbourg 2 luxenbourg 0
noway 0 neepal 0
-----