10517: 强迫症
Memory Limit：128 MB
Time Limit：2.000 S
Judge Style：Text Compare
Creator：
Submit：1
Solved：0
Description
2332933是一个严重的强迫症患者，现在他有一个无向图，这个无向图有n个点，m条边，现在可以修改一些边的长度改成任意非负整数，起点为1号点，终点为n号点。他想知道最少需要修改多少条边，可以使得起点到终点的最短路恰好为c。
Input
第一行T <= 10
接下来每个case：第一行3个整数n m c，(2 <= n <= 100, 1 <= m <= 500, s!=t, 0 <= c <= 1000000)，接下来m行每行3个整数，u,v,w(1 <= u,v <= n, u!=v,0 <= w <= 100000),表示u号点到v号点有一条长度为w的边。输入保证s到t连通，保证c不小于原图中1到n的最短路。
接下来每个case：第一行3个整数n m c，(2 <= n <= 100, 1 <= m <= 500, s!=t, 0 <= c <= 1000000)，接下来m行每行3个整数，u,v,w(1 <= u,v <= n, u!=v,0 <= w <= 100000),表示u号点到v号点有一条长度为w的边。输入保证s到t连通，保证c不小于原图中1到n的最短路。
Output
每个case输出"Case x: y",x为从1开始的编号，y为对应输入中询问的答案。
Sample Input Copy
1
3 2 1
1 2 10
2 3 1
Sample Output Copy
Case 1: 1
HINT
Author: zhaoweijie12