Status:  Past  Start:  20121013 12:15:00  End:  20121013 16:15:00 
The 2012 Caribbean National Contests of the ACMICPC (CUB)
Problem
2064  Interplanetary Warning System I
Created by  Carlos Joa Fong 
Added by  ymondelo20 (20121012) 
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?
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?
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?
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 N1 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.
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 N1 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 N1 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.
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 N1 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 N1 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.
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 N1 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 N1 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.
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 N1 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/