//Hints:Competitive programming books by Steven & Felix Halim
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz 123456
#define pii pair<int,int>
vector<pii>v[sz];
vector<pii>::iterator it;
int dist[sz]; //initializing distance of each node infinity
void dijkstra(int s){
priority_queue<pii, vector<pii>, greater<pii> >pq;
pq.push(make_pair(0,s)); //shorted in non-increasing order w.r.t distance so that the least distance can be pop out first
dist[s]=0;
while(!pq.empty()){
pii top=pq.top(); pq.pop();
int d=top.first; int u=top.second;
for(it=v[u].begin();it!=v[u].end();++it){
int v=it->first; int weight_u_v=it->second;
if(dist[u]+weight_u_v<dist[v]){
dist[v]=(dist[u]+weight_u_v);
pq.push(make_pair(dist[v],v));
}
}
}
}
int main()
{
int N,E,s,t,i,j,x,y,w,tc,cs=0;
scanf("%d",&tc);
while(tc--){
scanf("%d%d",&N,&E);
for(i=0;i<=N;i++)dist[i]=inf;
for(i=0;i<E;i++){
scanf("%d%d%d",&x,&y,&w);
v[x].push_back(make_pair(y,w));
v[y].push_back(make_pair(x,w));
}
dijkstra(1);
printf("Case %d: ",++cs);
if(dist[N]==inf)printf("Impossible\n");
else printf("%d\n",dist[N]);
for(int f=0;f<=N;f++)v[f].clear();
}
return 0;
}
Ly9IaW50czpDb21wZXRpdGl2ZSBwcm9ncmFtbWluZyBib29rcyBieSBTdGV2ZW4gJiBGZWxpeCBIYWxpbQojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIGluZiAweDNmM2YzZjNmCiNkZWZpbmUgc3ogMTIzNDU2CiNkZWZpbmUgcGlpIHBhaXI8aW50LGludD4KdmVjdG9yPHBpaT52W3N6XTsKdmVjdG9yPHBpaT46Oml0ZXJhdG9yIGl0OwppbnQgZGlzdFtzel07ICAvL2luaXRpYWxpemluZyBkaXN0YW5jZSBvZiBlYWNoIG5vZGUgaW5maW5pdHkKCnZvaWQgZGlqa3N0cmEoaW50IHMpewogICAgcHJpb3JpdHlfcXVldWU8cGlpLCB2ZWN0b3I8cGlpPiwgZ3JlYXRlcjxwaWk+ID5wcTsKICAgIHBxLnB1c2gobWFrZV9wYWlyKDAscykpOyAgICAvL3Nob3J0ZWQgaW4gbm9uLWluY3JlYXNpbmcgb3JkZXIgdy5yLnQgZGlzdGFuY2Ugc28gdGhhdCB0aGUgbGVhc3QgZGlzdGFuY2UgY2FuIGJlIHBvcCBvdXQgZmlyc3QKICAgIGRpc3Rbc109MDsKICAgIHdoaWxlKCFwcS5lbXB0eSgpKXsKICAgICAgICBwaWkgdG9wPXBxLnRvcCgpOyBwcS5wb3AoKTsKICAgICAgICBpbnQgZD10b3AuZmlyc3Q7IGludCB1PXRvcC5zZWNvbmQ7CiAgICAgICAgICAgIGZvcihpdD12W3VdLmJlZ2luKCk7aXQhPXZbdV0uZW5kKCk7KytpdCl7CiAgICAgICAgICAgICAgICBpbnQgdj1pdC0+Zmlyc3Q7IGludCB3ZWlnaHRfdV92PWl0LT5zZWNvbmQ7CiAgICAgICAgICAgICAgICBpZihkaXN0W3VdK3dlaWdodF91X3Y8ZGlzdFt2XSl7CiAgICAgICAgICAgICAgICAgICAgZGlzdFt2XT0oZGlzdFt1XSt3ZWlnaHRfdV92KTsKICAgICAgICAgICAgICAgICAgICBwcS5wdXNoKG1ha2VfcGFpcihkaXN0W3ZdLHYpKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9Cn0KaW50IG1haW4oKQp7CiAgICBpbnQgTixFLHMsdCxpLGoseCx5LHcsdGMsY3M9MDsKICAgIHNjYW5mKCIlZCIsJnRjKTsKICAgIHdoaWxlKHRjLS0pewogICAgc2NhbmYoIiVkJWQiLCZOLCZFKTsKICAgIGZvcihpPTA7aTw9TjtpKyspZGlzdFtpXT1pbmY7CiAgICBmb3IoaT0wO2k8RTtpKyspewogICAgICAgIHNjYW5mKCIlZCVkJWQiLCZ4LCZ5LCZ3KTsKICAgICAgICB2W3hdLnB1c2hfYmFjayhtYWtlX3BhaXIoeSx3KSk7CiAgICAgICAgdlt5XS5wdXNoX2JhY2sobWFrZV9wYWlyKHgsdykpOwogICAgfQoKICAgIGRpamtzdHJhKDEpOwogICAgcHJpbnRmKCJDYXNlICVkOiAiLCsrY3MpOwoKICAgICAgICBpZihkaXN0W05dPT1pbmYpcHJpbnRmKCJJbXBvc3NpYmxlXG4iKTsKICAgICAgICBlbHNlIHByaW50ZigiJWRcbiIsZGlzdFtOXSk7CgogICAgZm9yKGludCBmPTA7Zjw9TjtmKyspdltmXS5jbGVhcigpOwogICAgfQogICAgcmV0dXJuIDA7Cn0KCgo=