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的最短路。

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