[Jeremy Wu]冒险之路，平凡之路

夜煞（NightFury）是出自《驯龙高手2》中非常稀有且最危险聪明的龙，与其它龙的造型很不一样，类似蝙蝠，同时融合了猫科动物的体型以及野狼般精锐的眼神，身体附有黑色鳞片。体积娇小，表情动作灵巧可爱，双翼比例是龙里最大。翼面多达三对，因此飞行时间更长，速度更快更灵活。与其他龙所喷发的火焰不同，是伴随着电石气与氧气的幽蓝色球，在冲击或飞行一段距离后爆炸，攻击精准，格斗技能高超，高度智慧、体型较小、飞行和攻击能力优越。

现在，身为年轻英勇的维京勇士小嗝嗝的你，拥有一只叫没牙仔的夜煞。为了改变德雷格屠龙的观念，你们正在追赶嗜权的德雷格的路上。狡猾的德雷格躲在某个不知名的地方，但是聪明的你，利用手中的地图可以得某些地点之间的距离，也从他人口中得知了德雷格躲藏的地方。

现在已知没牙仔的飞行轨迹，博克岛的村民们非常想知道你和没牙仔在冒险过程中走过的总路程（同一段路线无须重复计算，但可能重复走）。如果在飞行轨迹途中遇到了德雷格，你会立马前往与德雷格见面，飞行结束。

有多组数据测试，以输入00结束。

对于每组输入数据，首先输入nt，表示有n个地点（n< 2000）。然后接下来有t行输入，每行输入abvalue表示a地点距离b地点value的长度，没有表明关系的地点不存在路,如果同一段路第二次输入的长度比先前的短，则a和b点间距离取短的那条。然后输入we，表示接下来有w行输入和德雷格所在的e点，每行输入cd表示没牙仔从c地点飞到d地点，且一定是相邻的两点，先后关系表示没牙仔先后经过的地点，保证不会经过不存在的路。

对于每组测试，输出“Case#k: ”，首先，k从1开始标号。

输出没牙仔在冒险过程中走过的总路程

7 8
1 2 3
2 3 4
3 4 5
4 5 6
4 5 1
5 6 3
5 6 4
6 8 1
6 8
1 2
2 3
3 4
4 5
5 6
6 8
5 4
1 2 3
2 3 4
3 4 10
4 5 15
11 4
1 2
2 1
1 2
2 3
3 2
2 1
1 2
2 3
3 4
4 5
5 6
0 0

Case #1: 17
Case #2: 17

Jeremy Wu