URI Online Judge | 1956


By Leandro Zatesko, UFFS BR Brazil

Timelimit: 2

Perhaps you don't know it, but not all elves have been gone away to Valinor. There are legends according to which some noldor live in an acacia forest to the north of Chapecó, although no mortal man has ever seen them, for over their houses lies an invisibility enchantment sung by Lady Galadriel just before she takes the last boat to the Immortal Lands. Each house has been built on the top of an acacia, and there are many elven robe bridges connecting pairs of houses, satisfying the following ancient tradition: if two elves belong to the same family but live in different houses, then it is possible to go from the house where one lives to the house where the other lives taking a path consisting only of elven robe bridges. Conversely, if two elves do not belong to the same family, they do not live in the same house, and any way of going from one's house to the other's mandatorily has to pass by the floor.

The Earth has already faced terrible threats, as the threat of Morgoth and the threat of Sauron. However, none is comparable to the threat that the men are being to the Earth by themselves. For the other day a careless smoker threw a cigarette end near the acacia forest and the fire spread. The elves got to save their houses, but all the bridges were destroyed. Now, they want to rebuild the bridges, but not all of them, since the elven robes made by the ancient noldor are very precious to them. They want to rebuild only the bridges which really are needed for the previously mentioned tradition to be satisfied again, and using as less as possible of elven robe. The task of deciding which bridges should be rebuilt has been appointed to you. If you do not find a way, no one else will.


The first input line consists of a single integer N (1 ≤ N ≤ 104), which represents the number of elven houses in the acacia forest, which are designated by the integers from 1 to N. Each ith (1 ≤ iN - 1) of the N - 1 lines following consists of a non-negative integer k followed by k pairs of integers j and cij (i < jN, 1 ≤ cij ≤ 106), indicating that there were a bridge between the houses i and j and rebuilding it costs cij metres of elven robe. Each bridge is described exactly once in the input and there are no more than 106 in total.


The output line shall consist of only two values, separated by a blank space, so that the first represents the number of elven families that live in the acacia forest and the second represents the minimum cost needed to rebuild the bridges in order to satisfy the ancient tradition.

Input Sample Output Sample

3 2 7 4 2 5 23
2 3 13 4 3
2 4 11 5 5
1 5 17

1 21