#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=