Stockbroker Grapevine

Stockbrokers are known to overreact to rumours. You have been hired to spread disinformation among a community of stockbrokers so that your employer gains a tactical edge in the stock market. To maximize the effect, the rumour must spread as fast as possible.

Each stockbroker only trusts information that arrives from their own contacts, so the structure of who talks to whom matters. Passing the rumour from one stockbroker to a specific contact takes a fixed number of minutes, and this passing time is directed: the time from person A to person B need not equal the time from B to A, and a connection may exist in only one direction.

Write a program that, for each community, decides which stockbroker you should tell the rumour first, and reports how long it then takes for the rumour to reach everyone. This duration is the time at which the last person receives the information.

The input contains several communities.

Each community begins with a line containing a single integer $N$, the number of stockbrokers ($1 \le N \le 100$). The stockbrokers are numbered from $1$ to $N$.

The next $N$ lines describe the contacts, one line per stockbroker in order. The line for a stockbroker begins with an integer $c$ ($0 \le c \le N-1$), the number of contacts that person can pass the rumour to, followed by $c$ pairs of integers. Each pair gives the number of a contact and the time in minutes ($1 \le t \le 10$) it takes that stockbroker to pass the rumour to that contact.

The input ends with a community whose first line is $0$; this terminating community is not processed.

For each community, print a single line.

If there is a stockbroker from whom the rumour can eventually reach every other stockbroker, print the number of the best starting stockbroker followed by a space and the time, in whole minutes, until the last person receives the rumour. Choose the starting stockbroker that minimizes this time; if several starting stockbrokers give the same minimum time, print the one with the smallest number.

If no starting stockbroker can reach the entire community (some person is unreachable no matter who starts the rumour), print disjoint instead.