SP26788 SHILL - Tiho Brdo

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.

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} $ .

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.