We heartily thank Kevin Bodurtha for creating this task!
Attention: this problem intentionally has a description in a form of whimsical space story. However it may be that some details are too unclear/obscure after all - in this case please do not hesitate to suggest corrections at forum!
The year is 3024. You're a space detective working a case in the Cygnus constellation. There are many
settlements spread very far apart in the constellation, and the Intergalactic Department of Transportation has
utilized wormhole technology to facilitate travel between settlements. Wormhole technology is somewhat difficult
to harness, but they have been able to construct the following system:
Assume that all settlements have synchronized clocks, so that time of day is constant across all settlements.
Actual use of these wormholes is somewhat uncommon and so for most of the day all of the wormholes remain unused. Still, the Department of Intergalactic Transportation publicly broadcasts the current wormhole configuration across the universe as a free service.
On a handful of occasions over the past year, a gang of pirates led by the infamous Captian Leo Potter have performed an amazing feat by taking advantage of a flaw in this transportation network. A few minutes after the wormholes reset and the new configuration have been broadcasted, they will rob an Intergalactic Bank at some "heist" settlement, then proceed to jump through every open wormhole in the network within the span of a few moments, thereby closing every available wormhole and blocking pursuit. By the time the wormholes reopen at the start of the next day, the pirates have already left their "getaway" settlement and sailed off into deep space, and the search must be called off before any progress can be made.
The Intergalactic Bank has branches at every settlement, and every settlement is surrounded by pirate-infested deep space, and so every settlement is a potential target. To make matters worse, your department has been hit hard by recent budget cuts, and can only spare 2 squads for a single day. With these limited resources, the plan is to send one squad to the "heist" settlement where the pirates will rob a bank, and the other squad to the "getaway" settlement the pirates will end up on after their sequence of jumps.
Some of your colleagues have also determined that not every day's wormhole layout would necessarily allow the pirates to jump through every single wormhole without missing any. They've determined this by taking some previous layouts and painstakingly tracing out every possible path that the pirates could have taken on that day, but apparently the pirates have figured out how to make such a determination much more quickly.
You sit down at your desk to try and make sense of everything as your phone starts ringing. Your undercover contacts have heard rumors that the Potter Pirates are planning to launch another heist shortly after the wormholes reset. Just then, the new wormhole layout for the day begins to print out on your intergalactic fax machine. You need to act fast!
Settlements are numbered sequentially, starting at 0.
Input data will contain N - the number of settlements in the first line.
The following lines describe the quantity of wormholes existing between each pair of settlements, in the
following format: A B W - where first two denote two settlements of a pair and W is quantity of wormholes.
there are lines for really every pair thus the total amount of lines could be calculated from N...
Answer should be two space-separated integers corresponding the "heist" and "getaway" settlements. List them in sequential order, without concern for which settlement may be the actual "heist" or "getaway" locations.
As the heist is imminent, you have just 3 minutes to solve the problem after you are given your input data;
so please reload the page to get new input before calculating and submitting the answer.
Example
input data:
10
0 1 19
0 2 18
0 3 10
0 4 19
0 5 18
0 6 17
0 7 19
0 8 10
0 9 19
1 2 19
1 3 12
1 4 15
1 5 18
1 6 14
1 7 18
1 8 14
1 9 11
2 3 17
2 4 19
2 5 11
2 6 18
2 7 18
2 8 19
2 9 13
3 4 15
3 5 15
3 6 10
3 7 13
3 8 10
3 9 14
4 5 13
4 6 16
4 7 17
4 8 19
4 9 19
5 6 14
5 7 13
5 8 11
5 9 19
6 7 16
6 8 14
6 9 19
7 8 15
7 9 11
8 9 12
answer:
0 9