#include<bits/stdc++.h>
using namespace std;
#define pb(x) push_back(x)
#define m_p(x,y) make_pair(x,y)
#define uu first
#define vv second

int dis[105], vis[105],n;
int dij(int x, vector<int>vec1[], vector<int>vec2[])
{
    priority_queue<pair<int,int> > pq;
    pq.push({0, x}),dis[x]=0;
    while(!pq.empty())
    {
        pair<int, int> p=pq.top(); pq.pop();
        int u=p.vv;
        if(u==n) return dis[n];
        for(int i=0; i<vec1[u].size(); i++)
        {
            int v=vec1[u][i], w=vec2[u][i];
            if(dis[v]>dis[u]+w) dis[v]=dis[u]+w, pq.push({dis[v], v});
        }
    }
    return -1;
}
int main()
{
    int t,z;
    scanf("%d",&t);
    for(z=1; z<=t; z++)
    {
        int i,j,k,l,x,y,u,v,m,w;
        scanf("%d %d",&n,&m);
        for(i=0; i<=n; i++) dis[i]=1e9;
        vector<int> vec1[105], vec2[105];
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            vec1[u].pb(v), vec2[u].pb(w);
            vec1[v].pb(u), vec2[v].pb(w);
        }
        v=dij(1, vec1,vec2);
        if(v==-1) printf("Case %d: Impossible\n",z);
        else printf("Case %d: %d\n",z,v);
    }
    return 0;
}