The Joker presents: Death of the BAT
Time Limit: 3 Seconds Memory Limit: 65536 KB
It's Christmas Eve, and BlackMask hired deadliest assassins to kill the Batman. The assassins are out in their separate region in Gotham City. BlackMask put $50 million on Batman's head, so assassins will start walking to the BlackMask's Hotel. Your job is to figure out which assassin gets to the BlackMask's Hotel first (the supplied test data will always have exactly one fastest assassin).
Each assassin is located in his/her own region, though some region have no assassins in them. Each region is connected by a path to one or more other regions (potentially including itself). Sometimes, two (potentially self-same) region are connected by more than one path. One or more of the regions has a path to the Hotel. Thus, all assassins have a path to the Hotel and they always know the shortest path. Of course, assassins can go either direction on a path and they all walk at the same speed.
The regions are labeled as assassin's names without any space ('KillerCroc', 'Bane', 'CopperHead', etc.) and ‘a’..’z’. Assassins are in the region that labeled with his/her name. No assassin is in a region labeled with a lower case letter. The Hotel's label is ‘J’; no assassins are in the Hotel, though.
Input
Line 1: Integer P (1 <= P <= 10000) the number of paths that interconnect the regions (and the Hotel)
Line 2..P+1: Space separated, two letters and an integer: the names of the interconnected regions/Hotel and the distance between them (1 <= distance <= 1000)
Output
A single line containing two items: the name of the assassin that arrives first back at the hotel, the length of the path followed by that assassin.
Sample Input
5 RedHood a 6 DeadShot a 3 FireFly b 9 a J 8 b J 3
Sample Output
DeadShot 11Submit