#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define maxx 5050
#define inf 1000000
int f[maxx];
vector<pii>G[maxx];
int dis[maxx];
int main() {
	 
	int t;
	cin>>t;
	int temp=t;
	while(t--)
	{   
		memset(dis,inf,sizeof dis);
		memset(f,0,sizeof f);
		int n,r;
		cin>>n>>r;
		while(r--)
		{
			int u,v,w;
			cin>>u>>v>>w;
			G[u].pb(mp(w,v));
			G[v].pb(mp(w,u));
		}
		dis[1]=0;
		priority_queue<pii,vector<pii>,greater<pii> >Q;
		Q.push(mp(0,1));
		while(!Q.empty())
		{
			int s=Q.top().second;
			Q.pop();
			for(int i=0;i<G[s].size();i++)
			{
				int V=G[s][i].second;
				int W=G[s][i].first;
				if(!f[V] && dis[V]>=dis[s]+W)
				{
					dis[V]=dis[s]+W;
					Q.push(mp(dis[V],V));
				}
			}
			f[s]=1;
		}
		printf("Case %d: %d\n",temp-t,dis[n]);
	}
	return 0;
}