简单的floyd运用

第一行输入一个整数C。C是测试的情况（0< C <=30）.第二行一个正整数N( 0< N <=100),表示道路的总数.紧接N行，每一行包含两个字符串， Si,，Ti，和一个整数Di,代表从Si到Ti的距离(0<= Di <=150)。最后一行有两个字符串，S 和 T，你得找出从S 到 T的最短的距离。地名是不超过120个小写字符的串（从‘a’到‘z’)。假设这里最多有100条直接连通两个地方的路。





Output



输出包含C行，每一行对一种测试情况。对每一种测试情况，输出包含一个整数，假如S 到 T存在一条最短的路,输出从S到T的最短距离,否则输出“-1”.



Sample Input





2

2

jiuzhouriver liuchi 89

liuchi liyuan 100

liuchi jiuzhouriver

3

youyongchi fengyuan 100

qinshi meiyuan 100

chaochang supermarkt 100

meiyuan youyongchi



Sample Output





89

-1