2064 - Interplanetary Warning System I

Created by Carlos Joa Fong
Added by ymondelo20 (2012-10-12)
Limits
Total Time: 20000 MS | Test Time: 6000 MS |Memory: 62 MB | Output: 64 MB | Size: 29 KB
Enabled languages
Available in

Description

After expelling the alien invaders, the United Federation of Planets has decided to install a warning system to alert them of any threat from these and other invaders. To do so, they will rely on their antiquated communication system, where each planet can communicate with its friendly neighboring planets. The system is set up so that every planet can send/receive messages (perhaps indirectly) to/from any other planet. And there is exactly one communication path between each pair of planets.

Due to the long distances between the planets, the communication link between two planets that are friendly to each other has some latency to transmit a message. You may assume that each planet takes no time to process and rebroadcast each message.

The Federation has N planets, each one conveniently identified by an integer from 1 to N.

For each pair of friendly planets u, v (1 <= u, v <= N), we know the time it takes to transmit a message from u to v. Let's call this D[u, v]. Since the transmission times are symmetrical, D[v, u] = D[u, v]).

The Federation wishes to pick a planet to monitor all alien threats and to warn the rest of the planets of an incoming invasion. To have enough time to prepare, they want to minimize the time it takes a message to reach all other planets from this source planet. Which planet should they select and how long does it take to warn all other planets?
After expelling the alien invaders, the United Federation of Planets has decided to install a warning system to alert them of any threat from these and other invaders. To do so, they will rely on their antiquated communication system, where each planet can communicate with its friendly neighboring planets. The system is set up so that every planet can send/receive messages (perhaps indirectly) to/from any other planet. And there is exactly one communication path between each pair of planets.

Due to the long distances between the planets, the communication link between two planets that are friendly to each other has some latency to transmit a message. You may assume that each planet takes no time to process and rebroadcast each message.

The Federation has N planets, each one conveniently identified by an integer from 1 to N.

For each pair of friendly planets u, v (1 <= u, v <= N), we know the time it takes to transmit a message from u to v. Let's call this D[u, v]. Since the transmission times are symmetrical, D[v, u] = D[u, v]).

The Federation wishes to pick a planet to monitor all alien threats and to warn the rest of the planets of an incoming invasion. To have enough time to prepare, they want to minimize the time it takes a message to reach all other planets from this source planet. Which planet should they select and how long does it take to warn all other planets?
After expelling the alien invaders, the United Federation of Planets has decided to install a warning system to alert them of any threat from these and other invaders. To do so, they will rely on their antiquated communication system, where each planet can communicate with its friendly neighboring planets. The system is set up so that every planet can send/receive messages (perhaps indirectly) to/from any other planet. And there is exactly one communication path between each pair of planets.

Due to the long distances between the planets, the communication link between two planets that are friendly to each other has some latency to transmit a message. You may assume that each planet takes no time to process and rebroadcast each message.

The Federation has N planets, each one conveniently identified by an integer from 1 to N.

For each pair of friendly planets u, v (1 <= u, v <= N), we know the time it takes to transmit a message from u to v. Let's call this D[u, v]. Since the transmission times are symmetrical, D[v, u] = D[u, v]).

The Federation wishes to pick a planet to monitor all alien threats and to warn the rest of the planets of an incoming invasion. To have enough time to prepare, they want to minimize the time it takes a message to reach all other planets from this source planet. Which planet should they select and how long does it take to warn all other planets?

Input specification

First line of input contains the number of test cases T (T <= 20) to follow.

Each test case starts with an empty line, followed by a line containing integer N (2 <= N <= 30,000), the number of planets in the federation. The next N-1 lines contain three integers u, v, and d (1 <= d <= 1000), where u and v are the IDs (between 1 and N) of two friendly planets that can communicate with each other, and d = D[u, v] is the time to transmit a message between these two planets.
First line of input contains the number of test cases T (T <= 20) to follow.

Each test case starts with an empty line, followed by a line containing integer N (2 <= N <= 30,000), the number of planets in the federation. The next N-1 lines contain three integers u, v, and d (1 <= d <= 1000), where u and v are the IDs (between 1 and N) of two friendly planets that can communicate with each other, and d = D[u, v] is the time to transmit a message between these two planets.
First line of input contains the number of test cases T (T <= 20) to follow.

Each test case starts with an empty line, followed by a line containing integer N (2 <= N <= 30,000), the number of planets in the federation. The next N-1 lines contain three integers u, v, and d (1 <= d <= 1000), where u and v are the IDs (between 1 and N) of two friendly planets that can communicate with each other, and d = D[u, v] is the time to transmit a message between these two planets.

Output specification

For each test case, output a single line with two space separated integers: the ID of the optimal planet the Federation should choose and the time this planet needs to warn all other planets. If several planets fit this criteria, pick the one with smaller ID.
For each test case, output a single line with two space separated integers: the ID of the optimal planet the Federation should choose and the time this planet needs to warn all other planets. If several planets fit this criteria, pick the one with smaller ID.
First line of input contains the number of test cases T (T <= 20) to follow.

Each test case starts with an empty line, followed by a line containing integer N (2 <= N <= 30,000), the number of planets in the federation. The next N-1 lines contain three integers u, v, and d (1 <= d <= 1000), where u and v are the IDs (between 1 and N) of two friendly planets that can communicate with each other, and d = D[u, v] is the time to transmit a message between these two planets.

Sample input

2

3
1 2 2
1 3 3

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

Sample output

1 3
6 12

Hint(s)

http://coj.uci.cu/contest/
http://coj.uci.cu/contest/
http://coj.uci.cu/contest/