The Fastest Road to Banikoara

Codjo: I am ready for the trip to Banikoara.

Bossi: Let us go through Parakou.

Assiba: No, the fastest road to go to Banikoara is through Djougou.

Your task is to write a program which, given a list of towns and distances between these towns, gives the shortest distance to travel from a town A to a town B.

Input Specification

The first line of the input contains a single integer P (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set begins with a line containing the number N of the remaining lines in the data set (1 ≤ N ≤ 500), followed by a space, followed by the name of the departure town, followed by a space, followed by the name of the destination town. Each of the next N lines contains the names of two towns separated by a space, followed by a space, followed by the distance (in kilometers) between the two towns. The distance will be an integer, and the town names will be strings consisting of uppercase and lowercase English letters and hyphens (“-”).

Output Specification

For each data set, you must generate a single output line containing the name of the departure town, followed by a space, followed by the name of the destination town, followed by a space, followed by the shortest distance to travel between the two towns.

Sample Input

1. 1
2. 4 Dassa-Zoume Banikoara
3. Dassa-Zoume Djougou 270
4. Banikoara Djougou 211
5. Parakou Banikoara 284
6. Parakou Dassa-Zoume 225

download as text file

Output for Sample Input

1. Dassa-Zoume Banikoara 481

download as text file