该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

现在的大学都非常大。中山大学有四个校区，分别是广州北校区、广州南校区、广州东校区和珠海校。每个校区里面又包含了很多建筑物。有时，老师和学生经常要从某个校区或校区之间的某个建筑物到另外一个建筑物，他们想让你帮忙，计算出它们之间的最短路。

Format

Input

输入中包括 C 组测试数据。（1<=c<=15）

对于每组测试数据，第一行为一个整数 N(0<N≤100)，表示路的条数。接下来的 N 行，第 i 行（1≤i≤N）包括两个字符串 Si，Ti 和一个整数 Di(0≤Di≤100)。表示 Si 到 Ti 有一条长为 Di 的路。

最后一行包含两个字符串 S 和 T，要我们求 S 到 T 的最短路径。Si，Ti，S，T 的格式都为：Campus.Place(某个校区的某个建筑物)。Campus 用：“North”，“South”，“East”，“Zhuhai”，表示，代表四个校区的名称，Place 为小于一百个字符的小写字母串，用 a-z中的字母表示。

Output

输出共 C 行，每行对应一组测试数据。对于每组数据，如果 S 到 T 有路，输出最短路，否则输出-1。

Samples

1
2
South.xiaolitang South.xiongdelong 2
South.xiongdelong Zhuhai.liyuan 100
South.xiongdelong South.xiaolitang

2

Limitation

1s, 1024KiB for each test case.