#include<bits/stdc++.h>
using namespace std ;
#define rep(i,a,b) for(int i=a; i<=b; i++)
#define per(i,b,a) for(int i=b; i>=a; i--)
#define sz(v) (int)v.size()
typedef long long ll ;
const int mod = 1e9 + 7 ;
ll powmod( ll a, ll b) { ll res = 1 ; while ( b) { if ( b& 1 ) res = ( res* a) % mod ; a = ( a* a) % mod ; b >>= 1 ; } return res ; }
const int maxn = 3e5 + 5 ;
const int inf = 1e9 ;
void solve( )
{
int n, m ;
cin >> n >> m ;
int dp[ 56 ] [ 56 ] ;
int gph[ 56 ] [ 56 ] ;
vector< pair< int , pair< int , int > > > edges ;
rep( i,0 ,n- 1 )
{
rep( j,0 ,n- 1 )
{
gph[ i] [ j] = 0 ;
dp[ i] [ j] = inf ;
}
}
rep( i,0 ,m- 1 )
{
int u, v, w ;
cin >> u >> v >> w ;
u-- ;
v-- ;
gph[ u] [ v] = w ;
gph[ v] [ u] = w ;
edges.push_back ( { u, { v, w} } ) ;
}
rep( i,0 ,n- 1 )
{
rep( j,0 ,n- 1 )
{
if ( i == j) dp[ i] [ j] = 0 ;
else if ( gph[ i] [ j] ! = 0 ) dp[ i] [ j] = gph[ i] [ j] ;
}
}
rep( k,0 ,n- 1 )
{
rep( i,0 ,n- 1 )
{
rep( j,0 ,n- 1 )
{
dp[ i] [ j] = min( dp[ i] [ j] , dp[ i] [ k] + dp[ k] [ j] ) ;
}
}
}
bool chk = true ;
rep( i,0 ,m- 1 )
{
int node1 = edges[ i] .first ;
int node2 = edges[ i] .second .first ;
int wt = edges[ i] .second .second ;
if ( dp[ node1] [ node2] ! = wt) chk = false ;
}
if ( ! chk)
{
cout << "impossible\n " ;
}
else
{
cout << m << "\n " ;
rep( i,0 ,m- 1 )
{
cout << edges[ i] .first + 1 << " " << edges[ i] .second .first + 1 << " " << edges[ i] .second .second << "\n " ;
}
}
}
int main( )
{
ios:: sync_with_stdio ( false ) ;
cin .tie ( NULL ) ;
freopen ( "Problem_id.txt" ,"r" ,stdin ) ;
freopen ( "Solution_id.txt" ,"w" ,stdout ) ;
int tc ;
cin >> tc ;
rep( t, 1 , tc)
{
cout << "Case #" << t << ": " ;
solve( ) ;
}
return 0 ;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZCA7CiNkZWZpbmUgcmVwKGksYSxiKSBmb3IoaW50IGk9YTsgaTw9YjsgaSsrKQojZGVmaW5lIHBlcihpLGIsYSkgZm9yKGludCBpPWI7IGk+PWE7IGktLSkKI2RlZmluZSBzeih2KSAoaW50KXYuc2l6ZSgpCnR5cGVkZWYgbG9uZyBsb25nIGxsIDsKY29uc3QgaW50IG1vZCA9IDFlOSArIDc7CmxsIHBvd21vZChsbCBhLCBsbCBiKSB7IGxsIHJlcyA9IDEgOyB3aGlsZShiKSB7IGlmKGImMSkgcmVzID0gKHJlcyphKSVtb2QgOyAgYSA9IChhKmEpJW1vZCA7IGIgPj49IDEgOyB9ICByZXR1cm4gcmVzIDsgfQpjb25zdCBpbnQgbWF4biA9IDNlNSArIDUgOwpjb25zdCBpbnQgaW5mID0gMWU5IDsKdm9pZCBzb2x2ZSgpCnsKICAgIGludCBuLCBtIDsKICAgIGNpbiA+PiBuID4+IG0gOwogICAgaW50IGRwWzU2XVs1Nl0gOwogICAgaW50IGdwaFs1Nl1bNTZdIDsKICAgIHZlY3RvcjxwYWlyPGludCwgcGFpcjxpbnQsIGludD4gPiA+IGVkZ2VzIDsKICAgIHJlcChpLDAsbi0xKQogICAgewogICAgICByZXAoaiwwLG4tMSkKICAgICAgewogICAgICAgICAgZ3BoW2ldW2pdID0gMCA7CiAgICAgICAgICBkcFtpXVtqXSA9IGluZiA7CiAgICAgIH0KICAgIH0KICAgIHJlcChpLDAsbS0xKQogICAgewogICAgICAgaW50IHUsIHYsIHcgOwogICAgICAgY2luID4+IHUgPj4gdiA+PiB3IDsKICAgICAgIHUtLSA7CiAgICAgICB2LS0gOwogICAgICAgZ3BoW3VdW3ZdID0gdyA7CiAgICAgICBncGhbdl1bdV0gPSB3IDsKICAgICAgIGVkZ2VzLnB1c2hfYmFjayh7dSwge3YsIHd9fSkgOwogICAgfQogICAgcmVwKGksMCxuLTEpCiAgICB7CiAgICAgICByZXAoaiwwLG4tMSkKICAgICAgIHsKICAgICAgICAgIGlmKGkgPT0gaikgZHBbaV1bal0gPSAwIDsKICAgICAgICAgIGVsc2UgaWYoZ3BoW2ldW2pdICE9IDApIGRwW2ldW2pdID0gZ3BoW2ldW2pdIDsKICAgICAgIH0KICAgIH0KICAgIHJlcChrLDAsbi0xKQogICAgewogICAgICAgcmVwKGksMCxuLTEpCiAgICAgICB7CiAgICAgICAgICByZXAoaiwwLG4tMSkKICAgICAgICAgIHsKICAgICAgICAgICAgZHBbaV1bal0gPSBtaW4oZHBbaV1bal0sIGRwW2ldW2tdICsgZHBba11bal0pIDsKICAgICAgICAgIH0KICAgICAgIH0KICAgIH0KICAgIGJvb2wgY2hrID0gdHJ1ZSA7CiAgICByZXAoaSwwLG0tMSkKICAgIHsKICAgICAgaW50IG5vZGUxID0gZWRnZXNbaV0uZmlyc3QgOwogICAgICBpbnQgbm9kZTIgPSBlZGdlc1tpXS5zZWNvbmQuZmlyc3QgOwogICAgICBpbnQgd3QgPSBlZGdlc1tpXS5zZWNvbmQuc2Vjb25kIDsKICAgICAgaWYoZHBbbm9kZTFdW25vZGUyXSAhPSB3dCkgY2hrID0gZmFsc2UgOwogICAgfQogICAgaWYoIWNoaykKICAgIHsKICAgICAgICBjb3V0IDw8ICJpbXBvc3NpYmxlXG4iIDsKICAgIH0KICAgIGVsc2UKICAgIHsKICAgICAgICBjb3V0IDw8IG0gPDwgIlxuIiA7CiAgICAgICAgcmVwKGksMCxtLTEpCiAgICAgICAgewogICAgICAgICAgICBjb3V0IDw8IGVkZ2VzW2ldLmZpcnN0ICsgMSA8PCAiICIgPDwgZWRnZXNbaV0uc2Vjb25kLmZpcnN0ICsgMSA8PCAiICIgPDwgZWRnZXNbaV0uc2Vjb25kLnNlY29uZCA8PCAiXG4iIDsKICAgICAgICB9CiAgICB9Cn0KaW50IG1haW4oKQp7CiAgICBpb3M6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSkgOwogICAgY2luLnRpZShOVUxMKSA7CiAgICBmcmVvcGVuKCJQcm9ibGVtX2lkLnR4dCIsInIiLHN0ZGluKTsKICAgIGZyZW9wZW4oIlNvbHV0aW9uX2lkLnR4dCIsInciLHN0ZG91dCkgOwogICAgaW50IHRjIDsKICAgIGNpbiA+PiB0YyA7CiAgICByZXAodCwgMSwgdGMpCiAgICB7CiAgICAgICBjb3V0IDw8ICJDYXNlICMiIDw8IHQgPDwgIjogIiA7CiAgICAgICBzb2x2ZSgpIDsKICAgIH0KICAgIHJldHVybiAwIDsKfQ==