#include <bits/stdc++.h>
#define dbg(i,j) cout<<"I am "<<i<<" = "<<endl<<j<<endl;
#define dbr(name,a) cout<<name<<endl;for(auto x:a)cout<<x<<" ";cout<<endl;
#define DBR(name,a) cout<<name<<endl;for(auto x:a){ for(auto y:x)cout<<y<<" ";cout<<endl;}
#define dbmp(name,a) cout<<name<<endl;for(auto x:a){ cout<<x.first<<"\t"<<x.second<<endl;}
#define dbp(name,a) cout<<name<<endl;cout<<a.first<<"\t"<<a.second<<endl;
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF  1000005
using namespace std;

typedef long long int big;

typedef  long double fig;

int n=0;
int dist[50][50];
int graph[50][50];

void floydWarshall ()
{
    //int dist[n][n];
    /* dist[][] will be the output matrix
    that will finally have the shortest
    distances between every pair of vertices */
    int  i, j, k;

    /* Initialize the solution matrix same
    as input graph matrix. Or we can say
    the initial values of shortest distances
    are based on shortest paths considering
    no intermediate vertex. */
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            dist[i][j] = graph[i][j];

    /* Add all vertices one by one to
    the set of intermediate vertices.
    ---> Before start of an iteration,
    we have shortest distances between all
    pairs of vertices such that the
    shortest distances consider only the
    vertices in set {0, 1, 2, .. k-1} as
    intermediate vertices.
    ----> After the end of an iteration,
    vertex no. k is added to the set of
    intermediate vertices and the set becomes {0, 1, 2, .. k} */
    for (k = 0; k < n; k++)
    {
        // Pick all vertices as source one by one
        for (i = 0; i < n; i++)
        {
            // Pick all vertices as destination for the
            // above picked source
            for (j = 0; j < n; j++)
            {
                // If vertex k is on the shortest path from
                // i to j, then update the value of dist[i][j]
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }

    // Print the shortest distance matrix
    //printSolution(dist);
}

int main(){
    freopen("i1.txt","rt",stdin);
    freopen("o1.txt","wt",stdout);
    int t;
    cin>>t;
    int test=1;
    while(t--){
        int m;
        cin>>n>>m;
        //int arr[n][n];
        for(big i=0;i<n;i++){
            for(big j=0;j<n;j++){
                graph[i][j]=INF;
            }
        }
        for(big i=0;i<m;i++){
            int x,y,z;
            cin>>x>>y>>z;
            x--;
            y--;
            graph[x][y]=z;
            graph[y][x]=z;
        }

        //int dist[n][n];
        floydWarshall();
        cout<<"Case #"<<test<<": ";
        /*for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cout<<dist[i][j]<<" ";
            }
            cout<<"\n";
        }*/
        int flag=0;
        int edges=0;
        for(big i=0;i<n;i++){
            for(big j=i+1;j<n;j++){
                if(graph[i][j]!=INF){
                    if(graph[i][j]!=dist[i][j]){
                        cout<<"Impossible"<<endl;
                        flag=1;
                    }
                    else{
                        edges++;
                    }
                }
            }
        }
        if(!flag){
            cout<<edges<<"\n";
            for(big i=0;i<n;i++){
                for(big j=i+1;j<n;j++){
                    if(graph[i][j]!=INF){
                        cout<<i+1<<" "<<j+1<<" "<<graph[i][j]<<"\n";
                    }
                }
            }
        }
        test++;
    }

    return 0;
}