题目描述

现在的大学都非常大

中山大学有四个校区，分别是广州北校区、广州南校区、广州东 校区和珠海校

每个校区里面又包含了很多建筑物

有时，老师和学生经常要从某个校区或 校区之间的某个建筑物到另外一个建筑物，他们想让你帮忙，计算出它们之间的最短路

输入格式

输入中包括 $\red C$ 组测试数据

对于每组测试数据，第一行为一个整数 $\red {N(0<N≤100)}$，表示 路的条数

接下来的 $\red N$ 行，第 $\red i$ 行($\red {1≤i≤N}$)包括两个字符串 $\red {S_i，T_i}$ 和一个整数 $\red {D_i}$($\red {0≤D_i ≤100}$)

表示 $\red {S_i}$ 到 $\red {T_i}$ 有一条长为 $\red {D_i}$ 的路

最后一行包含两个字符串$\red S$ 和 $\red T$，要我们求 $\red S$ 到 $\red T$ 的最短路径

$\red {S_i，T_i，S，T}$ 的格式都 为:Campus.Place(某个校区的某个建筑物)

Campus 用:“North”，“South”，“East”， “Zhuhai”，表示，代表四个校区的名称，Place 为小于一百个字符的小写字母串，用 $\red {a-z}$ 中的字母表示

输出格式

输出共 $\red C$ 行，每行对应一组测试数据

对于每组数据，如果 $\red S$ 到 $\red T$ 有路，输出最短路， 否则输出$\red {-1}$

样例

输入样例

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

输出样例

3