#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 = 0;
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(int i=1;i<=n;++i){
for(int e=i+1;e<=n;++e){
if(d[i][e]!=inf_int)
cout << i<<" "<<e<<" "<<d[i][e]<<"\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;
}
I3ByYWdtYSBHQ0Mgb3B0aW1pemUoIk9mYXN0IikKI3ByYWdtYSBHQ0MgdGFyZ2V0KCJzc2Usc3NlMixzc2UzLHNzc2UzLHNzZTQscG9wY250LGFibSxtbXgsYXZ4LHR1bmU9bmF0aXZlIikKCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnR5cGVkZWYgdW5zaWduZWQgbG9uZyBsb25nIHVsbDsKY29uc3QgaW50IGluZl9pbnQgPSAxZTkgKyAxMDA7CmNvbnN0IGxsIGluZl9sbCA9IDFlMTg7CnR5cGVkZWYgcGFpcjxpbnQsIGludD4gcGlpOwp0eXBlZGVmIHBhaXI8bGwsIGxsPiBwbGw7CnR5cGVkZWYgbG9uZyBkb3VibGUgZGJsOwojZGVmaW5lIHBiIHB1c2hfYmFjawpjb25zdCBkb3VibGUgcGkgPSAzLjE0MTU5MjY1MzU4OTg7CiNkZWZpbmUgZG91dCBpZihkZWJ1ZykgY291dAojZGVmaW5lIGZpIGZpcnN0CiNkZWZpbmUgc2Ugc2Vjb25kCiNkZWZpbmUgc3Agc2V0cHJlY2lzaW9uCiNkZWZpbmUgc3ooYSkgKGludChhLnNpemUoKSkpCiNkZWZpbmUgYWxsKGEpIGEuYmVnaW4oKSxhLmVuZCgpCmJvb2wgZGVidWcgPSAwOwpjb25zdCBpbnQgTUFYTiA9IDFlNiArIDEwMDsKY29uc3QgaW50IExPRyA9IDI1Owpjb25zdCBpbnQgbW9kID0gOTI0ODQ0MDMzOwpjb25zdCBpbnQgTVggPSA1ZTUgKyAxMDA7CnR5cGVkZWYgbG9uZyBsb25nIGxpOwpjb25zdCBsaSBNT0QgPSAxMDAwMDAwMDAwOTQ5NzQ3NzEzbGw7CgppbnQgZFs2NF1bNjRdOwp2b2lkIHNvbHZlKCkgewogICAgaW50IG4sbTsKICAgIGNpbiA+PiBuID4+IG07CiAgICBmb3IoaW50IGk9MTtpPD1uOysraSl7CiAgICAgICAgZm9yKGludCBlPTE7ZTw9bjsrK2UpewogICAgICAgICAgICBkW2ldW2VdID0gaW5mX2ludDsKICAgICAgICB9CiAgICAgICAgZFtpXVtpXSA9IDA7CiAgICB9CiAgICB2ZWN0b3I8cGFpcjxwaWksaW50PiA+IGVkZ2VzOwogICAgZm9yKGludCBpPTE7aTw9bTsrK2kpewogICAgICAgIGludCBhLGIsYzsKICAgICAgICBjaW4gPj4gYSA+PiBiID4+IGM7CiAgICAgICAgZFthXVtiXSA9IGM7CiAgICAgICAgZFtiXVthXSA9IGM7CiAgICAgICAgZWRnZXMucGIoe3thLGJ9LGN9KTsKICAgIH0KCiAgICBmb3IoaW50IGs9MTtrPD1uOysrayl7CiAgICAgICAgZm9yKGludCBpPTE7aTw9bjsrK2kpewogICAgICAgICAgICBmb3IoaW50IGU9MTtlPD1uOysrZSl7CiAgICAgICAgICAgICAgICBkW2ldW2VdID0gbWluKGRbaV1bZV0sZFtpXVtrXSArIGRba11bZV0pOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQoKCiAgICBmb3IoYXV0byB4OmVkZ2VzKXsKICAgICAgICBpbnQgYSxiOyB0aWUoYSxiKSA9IHguZmk7CiAgICAgICAgaW50IGMgPSB4LnNlOwogICAgICAgIGlmKGRbYV1bYl0hPWMpewogICAgICAgICAgICBjb3V0IDw8ICJJbXBvc3NpYmxlIiA8PCJcbiI7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAgICB9CgogICAgaW50IGNudCA9IDA7CiAgICBmb3IoaW50IGk9MTtpPD1uOysraSl7CiAgICAgICAgZm9yKGludCBlPWkrMTtlPD1uOysrZSl7CiAgICAgICAgICAgIGlmKGRbaV1bZV0hPWluZl9pbnQpCiAgICAgICAgICAgICAgICBjbnQrKzsKICAgICAgICB9CiAgICB9CiAgICBjb3V0IDw8IGNudDw8IlxuIjsKICAgIGZvcihpbnQgaT0xO2k8PW47KytpKXsKICAgICAgICBmb3IoaW50IGU9aSsxO2U8PW47KytlKXsKICAgICAgICAgICAgaWYoZFtpXVtlXSE9aW5mX2ludCkKICAgICAgICAgICAgY291dCA8PCBpPDwiICI8PGU8PCIgIjw8ZFtpXVtlXTw8IlxuIjsKICAgICAgICB9CiAgICB9Cgp9CgpzaWduZWQgbWFpbigpIHsKI2lmZGVmIHp4YwogICAgZGVidWcgPSAwOwogICAgZnJlb3BlbigiLi4vaW5wdXQudHh0IiwgInIiLCBzdGRpbik7CiAgICAgZnJlb3BlbigiLi4vb3V0cHV0LnR4dCIsICJ3Iiwgc3Rkb3V0KTsKI2Vsc2UKCiNlbmRpZiAvL3p4YwogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTsKICAgIGNpbi50aWUoMCk7CiAgICBjb3V0LnRpZSgwKTsKICAgIGNvdXQuc2V0Zihpb3M6OmZpeGVkKTsKICAgIGNvdXQucHJlY2lzaW9uKDIwKTsKCiAgICBpbnQgdCA9IDE7CiAgICBjaW4gPj4gdDsKICAgIC8vIHQgPSAxOwogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gdDsgKytpKSB7CiAgICAgICAgY291dCA8PCAiQ2FzZSAjIiA8PCBpIDw8ICI6IjsKICAgICAgICBzb2x2ZSgpOwogICAgIC8vICAgY291dCA8PCAiXG4iOwogICAgfQogICAgZXhpdCgwKTsKICAgIHQgPSAxOwogICAgd2hpbGUgKHQtLSkKICAgICAgICBzb2x2ZSgpOwogICAgaWYgKGRlYnVnKQogICAgICAgIGNlcnIgPDwgZW5kbCA8PCAidGltZSA6ICIgPDwgKDEuMCAqIGNsb2NrKCkgLyBDTE9DS1NfUEVSX1NFQykgPDwgZW5kbDsKfQ==