#include <bits/stdc++.h>
#include <random>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define int ll
typedef pair<int, int> pii;
typedef pair<pii, pii> piii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector< vi > vvi;
typedef vector< vvi > vvvi;
typedef vector<short> vs;
typedef vector<vs> vvs;
typedef vector<vvs> vvvs;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<ld> vld;
typedef vector<vld> vvld;
typedef vector<vvld> vvvld;
typedef vector<string> vst;
typedef vector<vst> vvst;
typedef pair<ld, ld> pld;
//typedef complex<double> base;

#define inmin(a, b) a = min(a, (b))
#define inmax(a, b) a = max(a, (b))
//#define mp(a, b) make_pair((a), (b))
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define sqr(x) ((x) * (x))
#define fori(i, n) for(int i = 0; i < int(n); ++i)
#define SZ(a) ((int)((a).size()))
#define watch(x) cerr << (#x) << " = " << (x) << endl;

#ifdef MAX_HOME
#define cerr cout
#else
#define cerr if (false) cerr
#endif

const double PI = 2 * acos(0.0);
#define rand dont_do_this_please_kek_lol
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());

const string DIGITS = "0123456789";
const string ALPH = "abcdefghijklmnopqrstuvwxyz";

template <class T0, class T1>
inline ostream & operator << (ostream &out, pair<T0, T1> &a) {
    return out << "{" << a.first << ", " << a.second << "}";
}

template <class T0, class T1, class T2>
inline ostream & operator << (ostream &out, tuple<T0, T1, T2> &a) {
    return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << "}";
}

template <class T0, class T1, class T2, class T3>
inline ostream & operator << (ostream &out, tuple<T0, T1, T2, T3> &a) {
    return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << ", " <<  get<3>(a) << "}";
}

template<class T>
inline ostream & operator << (ostream &out, vector<T> &a) {
    out << "[";
    fori (i, a.size())
        out << a[i] << vector<string>{", ", "]  "}[i + 1 == a.size()];
    return out;
}



void smain();

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

#ifdef MAX_HOME
    freopen("input.txt", "r", stdin);
    clock_t start = clock();
#else
    //    freopen("keke.in", "r", stdin);
//    freopen("kek.out", "w", stdout);
#endif
    cout << setprecision(12) << fixed;
    smain();
#ifdef MAX_HOME
    cout << "\n\n\n\nTOTAL EXECUTION TIME: " << float( clock () - start ) /  CLOCKS_PER_SEC << endl;
#endif
    return 0;
}

const int M = 1e9 + 7;
int MH , x;
int MH2, x2;
const int L = 1e5 + 10;
//int pwx[L];

int pw(int a, int n = M - 2) {
    int ret = 1;
    while (n) {
        if (n & 1)
            ret = (ll) ret * a % M;
        a = (ll) a * a % M;
        n >>= 1;
    }
    return ret;
}

ull hsh(vi a) {
    ull ret = 0;
    int ret2 = 0;
    for (auto item : a) {
        ++item;
        ret = (ll) ret * x % MH;
        ret = (ret + item) % MH;
        ret2 = (ll) ret2 * x2 % MH2;
        ret2 = (ret2 + item) % MH2;
    }
    ret = (ull)ret ^ (((ull)ret2) << 32);
    return ret;
}

const int N = 2020;

struct edge {
    int from, to, dig;
};
vector<edge> e;
vi g[N], rg[N];
bool can_use[N];
int q[N + N];

void bfs(int s) {
    int ql, qr;
    ql = qr = 0;
    q[qr++] = s;
    while (ql < qr) {
        int v = q[ql++];
        can_use[v] = true;
        for (int id : rg[v]) {
            int to = e[id].from;
            if (!can_use[to]) {
                can_use[to] = true;
                q[qr++] = to;
            }
        }
    }
}



void solve() {
    int n, m;
    cin >> n >> m;
    e.clear();
    fori (i, n) {
        g[i].clear();
        rg[i].clear();
        can_use[i] = false;
    }
    fori (iter, m) {
        int u, v, dig;
        cin >> u >> v >> dig;

        g[u].push_back(e.size());
        rg[v].push_back(e.size());
        e.push_back({u, v, dig});
    }

    bfs(1);
    vi prv;
    map<ull, int> was;
    vi s;
    prv = {0};
    was[hsh(prv)] = 0;

    for (int i = 0; ; ++i) {
        int mindig = 10;
        for (int v : prv) {
            for (int id : g[v]) {
                int to = e[id].to;
                if (can_use[to]) {
                    inmin(mindig, e[id].dig);
                }
            }
        }
        assert(mindig < 10);

        vi kek = prv;
        prv.clear();
        for (int v : kek) {
            for (int id : g[v]) {
                int to = e[id].to;
                if (can_use[to] && mindig == e[id].dig) {
                    prv.push_back(to);
                }
            }
        }
        sort(ALL(prv));
        prv.resize(unique(ALL(prv)) - prv.begin());

        s.push_back(mindig);
        if (binary_search(ALL(prv), 1)) {

            ll ans = 0;
            ll ten = pw(10);
            for (int k = 0; k < s.size(); ++k) {
                ans = (ans + (ll)s[k] * ten) % M;
                ten = ((ll) ten * pw(10)) % M;
            }

            cout << ans;
            return;
        }


        if (was.count(hsh(prv))) {

            int j = was[hsh(prv)];
            int lol = s.size();
            int len = lol - j;
            ll ans = 0;
            ll ten = pw(10);
            for (int k = 0; k < j; ++k) {
                ans = (ans + (ll)s[k] * ten) % M;
                ten = (ll) ten * pw(10) % M;
            }

            ll kek = 0;
            for (int k = j; k < lol; ++k) {
                kek *= 10;
                kek += s[k];
                kek %= M;
            }
            kek = (ll) kek * pw(pw(10, lol)) % M;

            kek = (ll) kek * pw(1LL + M - pw(pw(10, len))) % M;
            ans = (ans + kek) % M;
            cout << ans;
            return;
        }

        was[hsh(prv)] = i + 1;


    }
}

bool is_prime(int M) {
    for (int j = 2; j * j <= M; ++j) {
        if (M % j == 0)
            return false;
    }
    return true;
}

void smain() {

//    watch(31 * pw(1LL + M - pw(100)) % M);

    for (MH = rng() % 10000000 + 1000000000; !is_prime(MH); ++MH);
    for (x = rng() % 2000 + 2020; !is_prime(x); ++x);
    for (MH2 = rng() % 10000000 + 1000000000; !is_prime(MH2); ++MH2);
    for (x2 = rng() % 2000 + 2020; !is_prime(x2); ++x2);


    int t;
    cin >> t;

    for (int i = 1; i <= t; ++i) {
        cout << "Case #" << i << ": ";
        solve();
        if (i != t) {
            cout << '\n';
        }
    }


}