In the medieval ages, in the small town of Silent Hill lived a monster named Glutton, which loved terrorising the townsfolk. Many knights have tried to slay it, but none have been able to survive the encounter.

One day, a brave architect called Davis has decided to attack the Glutton. He found out that the monster actually consists of a bunch of parts, interconnected in such a way that each part may control other parts. The Glutton has exactly one part corresponding to its brain; a part not controlled by any other part. Furthermore, the Glutton may have one or more parts that do not control any other part---these correspond to its claws. For every claw there exists exactly one set of connections through which the brain (directly or indirectly) controls it. If Davis successfully manages to disconnect the brain from all the claws, the Glutton remains completely harmless.

Davis took advantage of his project skills in order to determine that one may assign a power w_xy required to sever each of the Glutton's direct connections x -> y. Davis wishes to invest a minimal total amount of power in order to disconnect the brain from all the claws, therefore he is interested in knowing which connections, left-to-right, he needs to destroy in order to achieve this. If there are multiple appropriate solutions, Davis would prefer to have the invested power early on be as small as possible, i.e. he would like to know the lexicographically smallest appropriate solution.

Blinded by the fame he would attain and the folks' cheers of "Thank you, brave Davis!" should he defeat the Glutton, Davis is too impatient to compute the solution; he has asked you for help.

Input

The first line of the standard input contains an integer n, representing the number of the Glutton's parts. The part with ID 1 always represents the brain. Afterwards, a description of all the parts follows in order, starting from the brain, up to the part with ID n, in order, as follows: 

• The first line contains an integer m_i, representing the number of parts directly controlled by the current part.
• If m_i = 0 holds, then the current part is a claw.
• Otherwise, the second line will contain an array a of m_i integers, representing the indices of the parts directly controlled by the current part, left-to-right.
• The third line will then contain an array w of m_i integers, such that the j-th member of w, w_j, represents the power necessary to destroy the connection through which the current part controls the j-th member of a, a_j.

Output

Write to the first line of the standard output a single integer representing the minimal total power required for Davis to disable the Glutton. Then, the second line should contain the lexicographically smallest sequence of powers required for severing each of the individual connections, provided in a left-to-right order. Separate individual elements of the sequence with a single space.

Example

Input:
7
2
2 5
4 7
2
3 4
2 3
0
0
2
6 7
1 6
0
0

Output:
11
4 1 6

Explanation

The figures below represent the sample testcase; the left figure represents the Glutton's initial state as provided by the input, and the right figure represents the optimal solution. The brain is denoted by a black background, and the claws are denoted by a red outline. The crossed and dashed connections represent the ones that Davis should destroy. There are two solutions that require the total power of 11; they are, in a left-to-right order, {4, 7} and {4, 1, 6}. We choose the lexicographically smaller out of the two as the final solution.

Constraints

• 2 <= n <= 10⁵;
• 1 <= w_j <= 10⁹;
• The total number of connections will always be n - 1, and for every claw there will exist a unique set of connections linking it to the brain.