Congratulations, you've landed a paid co-op position and can start working on gaining work experience and paying off all of those student loans... but the job is far, and air travel is expensive. Looking to squeeze a few extra dollars in savings, the quest is to find the cheapest possible flight, even if that requires multiple connections.

The flight search is to go from YYZ to SEA.

The input file DATA5.txt will contain 5 sets of input. Each set starts with an integer 1 < N <= 20 -- size of available data, followed by N lines describing the available flights, in the form of CODE1 CODE2 price. Codes are 3 character long airport codes, the prices are positive integer values.

The output file OUT5.txt will contain 5 lines, integer values for the cheapest total flights for each scenario.

Note: there will always be a possible flight path.

Note2: the flights are described in a single direction. That is "SEA YYZ 1" can not be taken to go from YYZ to SEA.

1
YYZ SEA 500
3
YYZ SEA 500
YYZ YVR 300
YVR SEA 100
		        

500
400