C++ :

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<math.h>

using namespace std;

#define INF 0x3f3f3f3f

struct Edge{
	int e,v;
};

int n,m,c;

vector<Edge> edge[11000];

void addedge(int x,int y,int v){
	Edge t;
	t.e = y;
	t.v = v;
	edge[x].push_back(t);	
}

int turn(int x,int dep){
	return x + n * (dep - 1);
}

int dist[11000];
bool inQ[11000];

void spfa(){
	queue<int> q;
	memset(inQ,false,sizeof(inQ));
	memset(dist,INF,sizeof(dist));
	dist[1] = 0;
	q.push(1);
	inQ[1] = true;
	while(!q.empty()){
		int now = q.front();
		q.pop();
		inQ[now] = false;
		for(int i = 0;i < edge[now].size();++i){
			if(dist[edge[now][i].e] > dist[now] + edge[now][i].v){
				dist[edge[now][i].e] = dist[now] + edge[now][i].v;
				if(!inQ[edge[now][i].e]){
					q.push(edge[now][i].e);
					inQ[edge[now][i].e] = true;
				}
			}
		}
	}
}

int main(){
	int T;
	scanf("%d",&T);
	for(int caseT = 1;caseT <= T;++caseT){
		for(int i = 0;i < 11000;++i)
			edge[i].clear();
		scanf("%d%d%d",&n,&m,&c);
		for(int i = 1;i <= m;++i){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			for(int j = 1;j <= n;++j){
				addedge(turn(u,j),turn(v,j + 1),0);
				addedge(turn(u,j),turn(v,j),w);
				addedge(turn(v,j),turn(u,j + 1),0);
				addedge(turn(v,j),turn(u,j),w);
			}
		}
		spfa();
		int ans = -1;
		if(dist[n] < c){
			ans = 1;
			printf("case1\n");
		}else if(dist[n] == c){
			ans = 0;
		}else{
			for(int i = 2;i <= n;++i){
				int t = turn(n,i);
				if(dist[t] <= c){
					ans = i - 1;
					break;
				}
			}
		}
		printf("Case %d: %d\n",caseT,ans);
	}
	return 0;
}