#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< int , int > pii;
typedef vector< int > vi;
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define FOR(i, a, b) for (int i=a; i<b; i++)
#define F0R(i, a) FOR(i, 0, a)
const int MAX = 50005 ;
const int MOD = 1000000007 ;
vector< pair< pii, int > > g[ MAX] ;
int deg[ MAX] ;
queue< int > q;
vi topo;
int dp[ MAX] [ 2 ] ;
// int mlp[MAX];
int main( ) {
int tc = 0 ;
while ( 1 ) {
// memset(mlp, 0, sizeof mlp);
F0R( i, MAX) { g[ i] .clear ( ) ; deg[ i] = 0 ; }
F0R( i, MAX) { F0R( j, 2 ) { dp[ i] [ j] = 0 ; } }
topo.clear ( ) ;
tc++ ;
int n, m;
scanf ( "%d %d" , & n, & m) ;
if ( n+ m == 0 ) { break ; }
F0R( i, m) {
int u, v, w; scanf ( "%d %d %d" , & u, & v, & w) ;
g[ u] .pb ( { { v, w} , i+ 1 } ) ;
deg[ v] ++ ;
}
/* topological sort */
FOR( i, 1 , n+ 1 ) { if ( deg[ i] == 0 ) { q.push ( i) ; } }
while ( ! q.empty ( ) ) {
int u = q.front ( ) ; q.pop ( ) ;
topo.pb ( u) ;
for ( auto i : g[ u] ) {
if ( -- deg[ i.f .f ] == 0 ) {
q.push ( i.f .f ) ;
}
}
}
/* code to find maximum longest path: for debugging */
/*
vector<pii> ans;
for (int k=(int)topo.size()-1; ~k; k--) {
int l = topo[k];
for (auto i : g[l]) { mlp[l] = max(mlp[l], mlp[i.f.f] + i.f.s); }
}
*/
/* compute the dp[i][0] */
for ( int k= ( int ) topo.size ( ) - 2 ; ~k; k-- ) {
int i = topo[ k] ;
dp[ i] [ 0 ] = MOD;
vi vals;
for ( auto j : g[ i] ) {
if ( dp[ j.f .f ] [ 0 ] ! = MOD) { vals.pb ( dp[ j.f .f ] [ 0 ] + j.f .s ) ; }
else { vals.clear ( ) ; break ; }
}
if ( ! vals.empty ( ) ) {
bool ok = true ;
for ( int j : vals) { if ( j ! = vals[ 0 ] ) { ok = false ; } }
if ( ok) { dp[ i] [ 0 ] = vals[ 0 ] ; }
}
}
/* compute the dp[i][1] */
for ( int k= ( int ) topo.size ( ) - 2 ; ~k; k-- ) {
int i = topo[ k] ;
dp[ i] [ 1 ] = MOD;
vector< pair< pii, int > > vals;
for ( auto j : g[ i] ) {
if ( dp[ j.f .f ] [ 0 ] ! = MOD) {
vals.pb ( { { dp[ j.f .f ] [ 0 ] + j.f .s , 0 } , j.s } ) ;
}
else if ( dp[ j.f .f ] [ 1 ] ! = MOD) {
vals.pb ( { { dp[ j.f .f ] [ 1 ] + j.f .s , 1 } , j.s } ) ;
}
else { vals.clear ( ) ; break ; }
}
sort( vals.begin ( ) , vals.end ( ) ) ;
if ( ! vals.empty ( ) ) {
bool sol = true ;
int maxi = vals.back ( ) .f .f ;
dp[ i] [ 1 ] = maxi;
for ( auto j : vals) {
if ( j.f .f ! = maxi) {
if ( j.f .s == 1 ) {
sol = false ;
break ;
}
ans.pb ( { j.s , maxi- j.f .f } ) ;
}
}
if ( ! sol) { dp[ i] [ 1 ] = MOD; }
}
}
if ( dp[ topo[ 0 ] ] [ 1 ] == MOD) { cout << "Case " << tc << ": No solution" << endl; }
else {
cout << "Case " << tc << ": " << ans.size ( ) << " " << dp[ topo[ 0 ] ] [ 1 ] << endl;
// for (pii i : ans) { cout << i.f << " " << i.s << endl; }
}
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKdHlwZWRlZiBwYWlyPGludCwgaW50PiBwaWk7CnR5cGVkZWYgdmVjdG9yPGludD4gdmk7CgojZGVmaW5lIGYgZmlyc3QKI2RlZmluZSBzIHNlY29uZAojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIG1wIG1ha2VfcGFpcgoKI2RlZmluZSBGT1IoaSwgYSwgYikgZm9yIChpbnQgaT1hOyBpPGI7IGkrKykKI2RlZmluZSBGMFIoaSwgYSkgRk9SKGksIDAsIGEpCgpjb25zdCBpbnQgTUFYID0gNTAwMDU7CmNvbnN0IGludCBNT0QgPSAxMDAwMDAwMDA3OwoKdmVjdG9yPHBhaXI8cGlpLCBpbnQ+ID4gZ1tNQVhdOwppbnQgZGVnW01BWF07CnF1ZXVlPGludD4gcTsKdmkgdG9wbzsKaW50IGRwW01BWF1bMl07Ci8vIGludCBtbHBbTUFYXTsKaW50IG1haW4oKSB7CiAgICBpbnQgdGMgPSAwOwogICAgd2hpbGUgKDEpIHsKICAgICAgICAvLyBtZW1zZXQobWxwLCAwLCBzaXplb2YgbWxwKTsKICAgICAgICBGMFIoaSwgTUFYKSB7IGdbaV0uY2xlYXIoKTsgZGVnW2ldID0gMDsgfQogICAgICAgIEYwUihpLCBNQVgpIHsgRjBSKGosIDIpIHsgZHBbaV1bal0gPSAwOyB9IH0KICAgICAgICB0b3BvLmNsZWFyKCk7CgogICAgICAgIHRjKys7CiAgICAgICAgaW50IG4sIG07CiAgICAgICAgc2NhbmYoIiVkICVkIiwgJm4sICZtKTsKICAgICAgICBpZiAobittID09IDApIHsgYnJlYWs7IH0KICAgICAgICBGMFIoaSwgbSkgewogICAgICAgICAgICBpbnQgdSwgdiwgdzsgc2NhbmYoIiVkICVkICVkIiwgJnUsICZ2LCAmdyk7CiAgICAgICAgICAgIGdbdV0ucGIoe3t2LCB3fSwgaSsxfSk7CiAgICAgICAgICAgIGRlZ1t2XSsrOwogICAgICAgIH0KCiAgICAgICAgLyogdG9wb2xvZ2ljYWwgc29ydCAqLwogICAgICAgIEZPUihpLCAxLCBuKzEpIHsgaWYgKGRlZ1tpXSA9PSAwKSB7IHEucHVzaChpKTsgfSB9CiAgICAgICAgd2hpbGUgKCFxLmVtcHR5KCkpIHsKICAgICAgICAgICAgaW50IHUgPSBxLmZyb250KCk7IHEucG9wKCk7CiAgICAgICAgICAgIHRvcG8ucGIodSk7CiAgICAgICAgICAgIGZvciAoYXV0byBpIDogZ1t1XSkgewogICAgICAgICAgICAgICAgaWYgKC0tZGVnW2kuZi5mXSA9PSAwKSB7CiAgICAgICAgICAgICAgICAgICAgcS5wdXNoKGkuZi5mKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgLyogY29kZSB0byBmaW5kIG1heGltdW0gbG9uZ2VzdCBwYXRoOiBmb3IgZGVidWdnaW5nICovCiAgICAgICAgLyoKICAgICAgICB2ZWN0b3I8cGlpPiBhbnM7CiAgICAgICAgZm9yIChpbnQgaz0oaW50KXRvcG8uc2l6ZSgpLTE7IH5rOyBrLS0pIHsKICAgICAgICAgICAgaW50IGwgPSB0b3BvW2tdOwogICAgICAgICAgICBmb3IgKGF1dG8gaSA6IGdbbF0pIHsgbWxwW2xdID0gbWF4KG1scFtsXSwgbWxwW2kuZi5mXSArIGkuZi5zKTsgfQogICAgICAgIH0KICAgICAgICAqLwogICAgICAgIAogICAgICAgIC8qIGNvbXB1dGUgdGhlIGRwW2ldWzBdICovCiAgICAgICAgZm9yIChpbnQgaz0oaW50KXRvcG8uc2l6ZSgpLTI7IH5rOyBrLS0pIHsKICAgICAgICAgICAgaW50IGkgPSB0b3BvW2tdOwogICAgICAgICAgICBkcFtpXVswXSA9IE1PRDsKICAgICAgICAgICAgdmkgdmFsczsKICAgICAgICAgICAgZm9yIChhdXRvIGogOiBnW2ldKSB7CiAgICAgICAgICAgICAgICBpZiAoZHBbai5mLmZdWzBdICE9IE1PRCkgeyB2YWxzLnBiKGRwW2ouZi5mXVswXStqLmYucyk7IH0KICAgICAgICAgICAgICAgIGVsc2UgeyB2YWxzLmNsZWFyKCk7IGJyZWFrOyB9CiAgICAgICAgICAgIH0KICAgICAgICAgICAgaWYgKCF2YWxzLmVtcHR5KCkpIHsKICAgICAgICAgICAgICAgIGJvb2wgb2sgPSB0cnVlOwogICAgICAgICAgICAgICAgZm9yIChpbnQgaiA6IHZhbHMpIHsgaWYgKGogIT0gdmFsc1swXSkgeyBvayA9IGZhbHNlOyB9IH0KICAgICAgICAgICAgICAgIGlmIChvaykgeyBkcFtpXVswXSA9IHZhbHNbMF07IH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICAKICAgICAgICAvKiBjb21wdXRlIHRoZSBkcFtpXVsxXSAqLwogICAgICAgIGZvciAoaW50IGs9KGludCl0b3BvLnNpemUoKS0yOyB+azsgay0tKSB7CiAgICAgICAgICAgIGludCBpID0gdG9wb1trXTsKICAgICAgICAgICAgZHBbaV1bMV0gPSBNT0Q7CiAgICAgICAgICAgIHZlY3RvcjxwYWlyPHBpaSwgaW50PiA+IHZhbHM7CiAgICAgICAgICAgIGZvciAoYXV0byBqIDogZ1tpXSkgewogICAgICAgICAgICAgICAgaWYgKGRwW2ouZi5mXVswXSAhPSBNT0QpIHsKICAgICAgICAgICAgICAgICAgICB2YWxzLnBiKHt7ZHBbai5mLmZdWzBdK2ouZi5zLCAwfSwgai5zfSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNlIGlmIChkcFtqLmYuZl1bMV0gIT0gTU9EKSB7CiAgICAgICAgICAgICAgICAgICAgdmFscy5wYih7e2RwW2ouZi5mXVsxXSArIGouZi5zLCAxfSwgai5zfSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNlIHsgdmFscy5jbGVhcigpOyBicmVhazsgfQogICAgICAgICAgICB9CiAgICAgICAgICAgIHNvcnQodmFscy5iZWdpbigpLCB2YWxzLmVuZCgpKTsKICAgICAgICAgICAgaWYgKCF2YWxzLmVtcHR5KCkpIHsKICAgICAgICAgICAgICAgIGJvb2wgc29sID0gdHJ1ZTsKICAgICAgICAgICAgICAgIGludCBtYXhpID0gdmFscy5iYWNrKCkuZi5mOwogICAgICAgICAgICAgICAgZHBbaV1bMV0gPSBtYXhpOwogICAgICAgICAgICAgICAgZm9yIChhdXRvIGogOiB2YWxzKSB7CiAgICAgICAgICAgICAgICAgICAgaWYgKGouZi5mICE9IG1heGkpIHsKICAgICAgICAgICAgICAgICAgICAgICAgaWYgKGouZi5zID09IDEpIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHNvbCA9IGZhbHNlOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgYW5zLnBiKHtqLnMsIG1heGktai5mLmZ9KTsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBpZiAoIXNvbCkgeyBkcFtpXVsxXSA9IE1PRDsgfQogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICBpZiAoZHBbdG9wb1swXV1bMV0gPT0gTU9EKSB7IGNvdXQgPDwgIkNhc2UgIiA8PCB0YyA8PCAiOiBObyBzb2x1dGlvbiIgPDwgZW5kbDsgfQogICAgICAgIGVsc2UgewogICAgICAgICAgICBjb3V0IDw8ICJDYXNlICIgPDwgdGMgPDwgIjogIiA8PCBhbnMuc2l6ZSgpIDw8ICIgIiA8PCBkcFt0b3BvWzBdXVsxXSA8PCBlbmRsOwogICAgICAgICAgICAvLyBmb3IgKHBpaSBpIDogYW5zKSB7IGNvdXQgPDwgaS5mIDw8ICIgIiA8PCBpLnMgPDwgZW5kbDsgfQogICAgICAgIH0KICAgIH0KfQo=