#OJ1546. Time Limit: 3 Sec  Memory Limit: 256 MB

Time Limit: 3 Sec  Memory Limit: 256 MB

Time Limit: 3 Sec  Memory Limit: 256 MB

Description

大鹏喜欢寻宝,这一天他来到一个墓穴中,墓穴由n个密室组成,密室编号为1到n,两个密室之间可能会有通道,如果有的话,通道内一定有一个亡灵,每个亡灵都有一个能力值w,代表着该亡灵的强弱,进入墓穴时大鹏被随机传送到一个密室中,宝物也是在随机的一个密室中,大鹏当然不想去碰到强大的亡灵,哪怕是多碰到几个稍弱一点的,但有时候是不得不遇到的,问题就是求出小明得到宝物时不得不遇到的最强大的亡灵的能力值。 第一组样例的墓穴结构如下图所示:

Input

第一行输入一个T 表示有T组测试用例。        每组测试用例的第一行包含三个整数n,s,q(2<=n<=100,s<=1000,q<=10000),n代表密室的个数,s代表通道的个数,q代表问题的个数。        之后s行每行包含三个整数c1,c2(c1!=c2),w(w<100000),w表示连接c1和c2密室的通道内的亡灵的能力值。        之后q行每行包含两个整数c3,c4(c3!=c4),c3表示大鹏开始所在的的密室编号,c4宝物所在的密室编号。

Output

对于每组测试数据首先输出一行Case x: 表示是第x组测试用例。        每个问题输出一行,输出为在该情况下大鹏所遇到的最强大的亡灵的能力值,如果大鹏无法得到宝物,输出“no path”。

Sample Input

2
7 9 3
1 2 50
1 3 60
2 4 120
2 5 90
3 6 50
4 6 80
4 7 70
5 7 40
6 7 140
1 7
2 6
6 2
7 6 3
1 2 50
1 3 60
2 4 120
3 6 50
4 6 80
5 7 40
7 5
1 7
2 4

Sample Output

Case 1:
80
60
60
Case 2:
40
no path
80

HINT

Append Code