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 Banikoara goes through Djougou.

You are given a list of roads between towns and the length of each road. Write a program that reports the shortest distance to travel from a town A to a town B.

Roads are two way. A road line in the input can be travelled in either direction. Two towns may be joined by more than one road, and a road may have the same town at both ends.

The first line contains one integer $P$ ($1 \le P \le 1000$), the number of data sets that follow.

Each data set begins with a line containing the number $N$ of remaining lines in the data set ($1 \le N \le 500$), a space, the name of the departure town, a space, and the name of the destination town. Each of the following $N$ lines contains the name of one town, a space, the name of another town, a space, and the distance in kilometers between those two towns.

Every distance is an integer between $1$ and $1000000$. A town name is a string of at most $30$ characters formed with [a-z], [A-Z] and the sign "-", and names are case sensitive. A route from the departure town to the destination town always exists.

For each data set, print one line containing the name of the departure town, a space, the name of the destination town, a space, and the shortest distance to travel between those two towns.

If the departure town and the destination town are the same, the shortest distance is $0$.