当前没有测试数据。

小明来到杭州旅游时获得了一本杭州市内公交大全，他发现即使起点和目的地相同，也有不同路线，请帮他找出用时最短的路线。 给出起点，终点以及所有公交线路。请输出最短用时！ （每条线路给出两个地点，来回往返）

Input

输入数据有多组，每组的第一行是线路的总数N(0<=N<=10000)； 第二行有小烤的所在地start，他的目的地end； 接着有n行，每行有站名s，站名e，以及从s到e的时间整数t(0<t<100)( 每个地名是一个长度不超过30的字符串)。 note：一组数据中地名数不会超过150个。 如果N== -1，表示输入结束。

Output

如果能到达目的地，输出最短的时间；否则，输出“-1”。

6
xiasha westlake
xiasha station 60
xiasha ShoppingCenterofHangZhou 30
station westlake 20
ShoppingCenterofHangZhou supermarket 10
xiasha supermarket 50
supermarket westlake 10
-1

50

HDU Today HDU - 2112