Problem

In 19XX, the Allied Forces were formed in n countries. Each country belonging to the Allied Forces has set up one or more bases in the country to protect itself from the invasion of enemy forces and is on the alert. Figure 1 shows an example of an Allied country, where the rectangle represents each country and the circle within it represents the base of that country.

Figure 1
Figure 1

When an enemy army invades, the information is to be transmitted from the base where it was first discovered to the bases of other countries or own countries belonging to the Allied Forces. It costs a positive integer to convey information to other locations.

In addition, each country has exactly one base to which soldiers belonging to the Allied Translator and Interpreter Section (ATIS) are assigned. Only this soldier can speak the language of all countries belonging to the Allied Forces, and the other soldiers can only speak the language of their own country. Therefore, when the base that received the information tries to convey the information to another country, if the base does not have soldiers belonging to ATIS, the information is transmitted from there to the base having soldiers belonging to ATIS in the home country and the information is sent to other countries. Need to be sent.

Each country is assigned a number from 0 to [the number of bases in that country-1], and the 0th base has soldiers belonging to ATIS. In other words, only the 0th base can transmit information to the bases in other countries, and communication from other bases to other countries is not possible. In addition, if the information is transmitted to the 0th base of the country, it is assumed that the information is transmitted to the whole country.

Communication is not possible between all bases for various reasons. Even if information can be transmitted from one base to another, the opposite is not always true. In addition, the cost of transmitting information from one base to another is not always the same as the cost of transmitting information to another base.

Based on these facts, I would like to know the transmission method with the lowest total cost of disseminating information to the entire Allied army when a base discovers an enemy army. It is assumed that the information has been distributed to the entire Allied Forces when the information is transmitted from the base where the enemy army is first found to the 0th base of all the countries belonging to the Allied Forces.

Since the base where the enemy army was found is given as a question, output the method of transmitting the information to the entire Allied army and its cost at the lowest cost.

For example, consider the following case (Sample Input 4, first question)

Suppose the first base of the country neepal discovers an enemy army. In this case, since it is not possible to communicate from the first base to another country, the information is first transmitted to the 0th base in the home country.

Next, the information is transmitted from the 0th base to the country luxenbourg, noway. It is possible to communicate directly from neepal to the 0th base of luxenbourg, but it is cheaper to convey the information to the 3rd base and then to the 0th base. In this case, the minimum cost to convey information to the 0th country of all countries is 12. There are multiple transmission methods that cost only 12, but one of them may be output as the answer.

The red arrow in Figure 2 below is one of the answers.

<image>
Figure 2

Constraints

• 1 ≤ n ≤ 26
• 1 ≤ mi ≤ 100
• 0 ≤ e ≤ 322400
• 0 ≤ costi ≤ 100
• 1 ≤ q ≤ 10
• countryname is a character string consisting of lowercase letters ‘a’ to ‘z’ and having a length of 1 or more and 20 or less.
• No more than one country with the same name will be given
• When c1i and c2i of the pair of communicable bases are the same, v1i and v2i are different
• When c1i and c2i of the pair of communicable bases are different, v1i is always 0.

Input

n
countryname0 m0
countryname1 m1
...
countrynamen-1 mn-1
e
c10 v10 c20 v20 cost0
c11 v11 c21 v21 cost1
...
c1e-1 v1e-1 c2e-1 v2e-1 coste-1
q
c30 v30
c31 v31
...
c3q-1 v3q-1

• n represents the number of countries belonging to the Allied Forces
• countrynamei is the name of the i-th country belonging to the Allied Forces, and mi is the number of bases in the i-th country.
• e represents the number of pairs of bases that can communicate
• The following e-line is given the cost cost of transmitting information from the base v1i in country c1i to the base v2i in country c2i.
• q represents the number of questions
• The following line q is given the name c3i of the country where the enemy army was found and its base v3i.
• c1i, c2i, c3i are any of the countries belonging to the Allied Forces
• v1i, v2i, v3i can never be more than the number of bases in the country

Output

The answer to each question is output in the following format.

On the last line of the answer to each question, print one line of 5'-', "-----" (excluding ").

If the answer exists

The first line outputs the minimum cost required to disseminate information from the country base given in the question to the entire Allied Forces.

The transmission method at that time is output on the second and subsequent lines. The transmission method is expressed in the following format.

c40 v40 c50 v50
c41 v41 c51 v51
...

Indicates that information has been transmitted from the base v4i in country c4i to the base v5i in country c5i.

Be careful of the following.

• It is not necessary to output in the order in which communication was performed
• If there is one or more transmission methods that minimize the total cost, one of them should be output.
• Do not output the same communicable pair more than once
• c4i, c5i must be one of the countries given in the input
• v4i, v5i must be less than the number of bases in the country

If the answer does not exist

Print “Impossible” (excluding “)” on one line.

Examples

Input

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

Output

20
usi 0 frence 0
frence 0 powland 0

Impossible

Input

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

Output

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

Input

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

Output

10
chinax 0 austraria 0
austraria 0 ok 0

7
ok 0 austraria 1
austraria 1 austraria 0
austraria 0 chinax 0

Input

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

Output

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

见题面

见题面