#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; }
        }
    }
}