#pragma GCC optimize("Ofast")
    #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
     
    #include <bits/stdc++.h>
     
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    const int inf_int = 1e9 + 100;
    const ll inf_ll = 1e18;
    typedef pair<int, int> pii;
    typedef pair<ll, ll> pll;
    typedef long double dbl;
    #define pb push_back
    const double pi = 3.1415926535898;
    #define dout if(debug) cout
    #define fi first
    #define se second
    #define sp setprecision
    #define sz(a) (int(a.size()))
    #define all(a) a.begin(),a.end()
    bool debug = 0;
    const int MAXN = 1e6 + 100;
    const int LOG = 25;
    const int mod = 924844033;
    const int MX = 5e5 + 100;
    typedef long long li;
    const li MOD = 1000000000949747713ll;
     
    int d[64][64];
    void solve() {
        int n,m;
        cin >> n >> m;
        for(int i=1;i<=n;++i){
            for(int e=1;e<=n;++e){
                d[i][e] = inf_int;
            }
            d[i][i] = 0;
        }
        vector<pair<pii,int> > edges;
        for(int i=1;i<=m;++i){
            int a,b,c;
            cin >> a >> b >> c;
            d[a][b] = c;
            d[b][a] = c;
            edges.pb({{a,b},c});
        }
     
        for(int k=1;k<=n;++k){
            for(int i=1;i<=n;++i){
                for(int e=1;e<=n;++e){
                    d[i][e] = min(d[i][e],d[i][k] + d[k][e]);
                }
            }
        }
     
     
        for(auto x:edges){
            int a,b; tie(a,b) = x.fi;
            int c = x.se;
            if(d[a][b]!=c){
                cout << "Impossible" <<"\n";
                return;
            }
        }
     
        int cnt = (int)edges.size();
        /*for(int i=1;i<=n;++i){
            for(int e=i+1;e<=n;++e){
                if(d[i][e]!=inf_int)
                    cnt++;
            }
        }*/
        cout << cnt<<"\n";
        for(auto x: edges){
            cout<<x.first.first<<" "<<x.first.second<<" "<<x.second<<"\n";
        }
     
    }
     
    signed main() {
    #ifdef zxc
        debug = 0;
        freopen("../input.txt", "r", stdin);
         freopen("../output.txt", "w", stdout);
    #else
     
    #endif //zxc
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        cout.setf(ios::fixed);
        cout.precision(20);
     
        int t = 1;
        cin >> t;
        // t = 1;
        for (int i = 1; i <= t; ++i) {
            cout << "Case #" << i << ":";
            solve();
         //   cout << "\n";
        }
        exit(0);
        t = 1;
        while (t--)
            solve();
        if (debug)
            cerr << endl << "time : " << (1.0 * clock() / CLOCKS_PER_SEC) << endl;
    }