| 描述 |
|---|
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 |
|
| 来源 |
| 第六届编程大赛 |