Stockbroker Grapevine#3219
Stockbrokers are known to overreact to rumours. You have been asked to develop a method to spread important news or information among a group of brokers in the fastest possible way.
Unfortunately, stockbrokers only trust news coming from their 'trusted sources'. This means you have to take into account the structure of their contacts when spreading the news. It takes a certain amount of time for a specific broker to pass the information to each of their colleagues. Your task is to write a program that tells you which person to choose as your starting point so that the information reaches everyone as quickly as possible. The duration is measured as the time when the last person receives the information.
Your program will input data for different sets of brokers. Each set starts with a line giving the number of brokers. Following this is a line for each broker, which contains the number of people with whom they have contact, who these people are, and the time taken to pass the message to each person. The format for each broker's line is as follows: the line starts with the number of contacts (), followed by pairs of integers, one for each contact. Each pair lists first a number referring to the contact (e.g., a '1' means person number one in the set), followed by the time in minutes taken to pass a message to that person. There are no special punctuation symbols or spacing rules.
For each data set, your program must output a single line containing the person who results in the fastest message transmission, and how long it will take before the last person receives any given message after you give it to that person, measured in integer minutes.
Each person is numbered 1 through to the number of brokers. The time taken to pass the message on will be between and minutes (inclusive), and the number of contacts will range between and one less than the number of brokers. The number of brokers will range from to . The input file is terminated by a set containing (zero) people.
It is possible that your program will receive a network of connections that excludes some persons, i.e., some people may be unreachable. If your program detects such a broken network, simply output the message "disjoint". Note that 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.
Example 1