1100:廉价航空

时间限制: 2 S | 内存限制: 65536 KB
Accept: 4 | Submit: 13
[提交] [状态] [讨论版]
描述

XY生活在A城市,想坐飞机去B城市看望JG。有一种方法是买A飞到B的机票,还有一种方法是转机(例如A先飞C,C飞D,D飞B,转机可以途经任意多个城市)。有的时候转机机票的总和会比直达的便宜。

某些城市之间并没有直达的航班,如果有航班,则有唯一的机票价格(即不会出现从x飞到y有多条不同的价格信息)。另外由于x飞到y和y飞到x的价格有可能是不同的,故如果x到y之间有往返直达航班,则会有两条记录,分别是x到y的价格和y到x的价格。

XY希望找到最便宜的航空费用。

输入

一个正整数n,表示有n组案例。

每组案例中,首先是一个正整数m(m<=100),表示航线的数量,以及两个字符串A和B,表示起点城市名字和终点城市名字。

然后是m行数据,每行数据代表一条航线的信息,由两个字符串x和y,以及一个整数p组成,代表从x城市飞到y城市的机票价格是p元。(1<=p<=5000)


输出

针对每组案例,输出一个整数,表示从A到B最便宜的费用(直达或者转机皆可)。如果从A直达或者转机都无法到达B,则输出-1。

每组案例输出完都要换行。


样例输入

2

4 Xiamen Beijing

Xiamen Beijing 1000

Xiamen Shanghai 400

Shanghai Xiamen 300

Shanghai Beijing 250

3 Xiamen Beijing

Xiamen Shanghai 400

Shanghai Tianjin 200

Xiamen Chengdu 800

样例输出

650

-1


HINT

 

来源
第六届编程大赛