Bungling Bureaucracy

(Hard Problem No# 4)

Modern offices work by passing messages from one employee to the next. As the director of a large company, you are interested in finding a method by which you can determine the best person to give messages to such that everyone in the company gets the message as soon as possible.

You know that your employees only speak with the people in their direct contact in the office, and you also know that for each each employee it will take a certain amount of time to pass the message onto each of their contacts. You need to write a program to determine the person who, when given the message, results in everyone receiving the message within the shortest possible time. In this instance, you are only interested in the time taken for the last person to get the message.

Your program will input data for different sets of employees. Each set starts with a line with the number of employees. Following this is a line for each employee which contains the number of people who they have contact with, who these people are, and the time taken for them to pass the message to each person. The format of the employee line is the number of contacts, followed by a pair of integers for each contact, these being who the contact is and the time taken to pass the message to this person, in minutes. For each set of data, your program must output a single line containing the person who results in the fastest message transmission, and how long before the last person will receive any given message after you give it to this person, measured in integer minutes.

Each person is numbered 1 through to the number of employees. The time taken to pass the message on will be between 1 and 10 minutes, and the number of contacts will range between 0 and one less than the number of employees. The number of employees will range from 1 to 100. The input file is terminated by a set of employees containing 0 (zero) people.

Assume that the input contains a connection of people such that there is at at least one person who will start with the message such that everyone else will eventually receive it. The time taken to pass the message from person A to person B is not necessarily the same as the time taken to pass it from B to A, if such transmission is possible at all.

SAMPLE INPUT

3
2 2 4 3 5
2 1 2 3 6
2 1 2 2 2
5
3 4 4 2 8 5 3
1 5 8
4 1 6 4 10 2 7 5 2
0
2 2 5 1 5
0

SAMPLE OUTPUT

3 2
5 5