E - El Arbolito de Navidad de Fito

Time limit: 1 s
Memory limit: 128 MiB
Languages: C, C++, Java, JavaScript, ... (details)

Fito está arreglando el arbolito de navidad y nuestra tarea es ayudarlo. El problema es que  el sobrino de Fito hizo un desmadre cuando organizo el árbol de navidad. El problema se puede modelar de la siguiente manera: hay n cajas en cada uno de los “vertices” del árbol, cada una está numerada de 1 a N(1<=N<=10000). Cada caja está vacía o contiene un número de bolas de navidad. La cantidad de bolas de navidad es N.

Lo que debemos de hacer es mover las bolas de navidad para que cada caja contenga una sola bola. Esto se debe de hacer realizando varios movimientos. En cada movimiento solo podemos mover una bola a una caja adyacente.  Para poder cenar a tiempo debemos de hacer esto en la menor cantidad de movimientos.

Input

Cada entrada contiene varios casos de prueba. La primera línea de cada caso de prueba es un numero N, seguido de N líneas, cada una de estas líneas contiene al menos tres números, V el número del vértice del árbol, seguido del número de bolas que contiene y luego   el numero D que identifica la cantidad de hijos del vértice V, seguido de V números que identifican los vértices hijos del vértice V. La entrada termina cuando N=0 y este caso no se debe de procesar.

Output

Por cada caso se debe de imprimir en una línea la cantidad mínima de movimientos que de debe de hacer en el árbol para que quede una sola bola en cada caja.

Sample test(s)

Input
9 1 2 3 2 3 4 2 1 0 3 0 2 5 6 4 1 3 7 8 9 5 3 0 6 0 0 7 0 0 8 2 0 9 0 0 9 1 0 3 2 3 4 2 0 0 3 0 2 5 6 4 9 3 7 8 9 5 0 0 6 0 0 7 0 0 8 0 0 9 0 0 9 1 0 3 2 3 4 2 9 0 3 0 2 5 6 4 0 3 7 8 9 5 0 0 6 0 0 7 0 0 8 0 0 9 0 0 0
Output
7 14 20