#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;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgbXAgbWFrZV9wYWlyCiNkZWZpbmUgcGlpIHBhaXI8aW50LGludD4KI2RlZmluZSBtYXh4IDUwNTAKI2RlZmluZSBpbmYgMTAwMDAwMAppbnQgZlttYXh4XTsKdmVjdG9yPHBpaT5HW21heHhdOwppbnQgZGlzW21heHhdOwppbnQgbWFpbigpIHsKCSAKCWludCB0OwoJY2luPj50OwoJaW50IHRlbXA9dDsKCXdoaWxlKHQtLSkKCXsgICAKCQltZW1zZXQoZGlzLGluZixzaXplb2YgZGlzKTsKCQltZW1zZXQoZiwwLHNpemVvZiBmKTsKCQlpbnQgbixyOwoJCWNpbj4+bj4+cjsKCQl3aGlsZShyLS0pCgkJewoJCQlpbnQgdSx2LHc7CgkJCWNpbj4+dT4+dj4+dzsKCQkJR1t1XS5wYihtcCh3LHYpKTsKCQkJR1t2XS5wYihtcCh3LHUpKTsKCQl9CgkJZGlzWzFdPTA7CgkJcHJpb3JpdHlfcXVldWU8cGlpLHZlY3RvcjxwaWk+LGdyZWF0ZXI8cGlpPiA+UTsKCQlRLnB1c2gobXAoMCwxKSk7CgkJd2hpbGUoIVEuZW1wdHkoKSkKCQl7CgkJCWludCBzPVEudG9wKCkuc2Vjb25kOwoJCQlRLnBvcCgpOwoJCQlmb3IoaW50IGk9MDtpPEdbc10uc2l6ZSgpO2krKykKCQkJewoJCQkJaW50IFY9R1tzXVtpXS5zZWNvbmQ7CgkJCQlpbnQgVz1HW3NdW2ldLmZpcnN0OwoJCQkJaWYoIWZbVl0gJiYgZGlzW1ZdPj1kaXNbc10rVykKCQkJCXsKCQkJCQlkaXNbVl09ZGlzW3NdK1c7CgkJCQkJUS5wdXNoKG1wKGRpc1tWXSxWKSk7CgkJCQl9CgkJCX0KCQkJZltzXT0xOwoJCX0KCQlwcmludGYoIkNhc2UgJWQ6ICVkXG4iLHRlbXAtdCxkaXNbbl0pOwoJfQoJcmV0dXJuIDA7Cn0=

MgozIDMKMSAyIDEwMAoyIDMgMjAwCjEgMyA1MAo0IDQKMSAyIDEwMAoyIDQgMjAwCjIgMyAyNTAKMyA0IDEwMA==

2
3 3
1 2 100
2 3 200
1 3 50
4 4
1 2 100
2 4 200
2 3 250
3 4 100