#include <bits/stdc++.h>

using namespace std;

struct Hist {
  int node, par;
};

const int kMod = 1e9 + 7;

int inv(int x) {
  int e = kMod - 2;
  int r = 1;
  while (e) {
    if (e % 2) r = 1LL * r * x % kMod;
    x = 1LL * x * x % kMod;
    e /= 2;
  }
  return r;
}
int Out(string s) {
  int ret = 0;
  for (auto c : s) {
    ret = 10LL * ret + c - '0';
    ret %= kMod;
  }
  return ret;
}


int main() {
  int t; cin >> t;
  for (int tt = 1; tt <= t; ++tt) {
    int n, m; cin >> n >> m;
    vector<vector<pair<int, int>>> graph(n);
    vector<vector<int>> trans(n);
    vector<int> avail(n, false);

    for (int i = 0; i < m; ++i) {
      int a, b, c; cin >> a >> b >> c;
      graph[a].emplace_back(b, c);
      trans[b].push_back(a);
    }
    graph[1].emplace_back(1, 0);

    vector<int> q;
    auto push = [&](int node) {
      if (avail[node]) return;
      avail[node] = true;
      q.push_back(node);
    };
    push(1);
    for (int i = 0; i < (int)q.size(); ++i)
      for (auto vec : trans[q[i]])
        push(vec);
    assert(avail[0]);

    string sol = "";

    vector<bool> seen(n, false);

    vector<Hist> hist;
    hist.push_back(Hist{0, -1});
    int old_sz = 0;

    for (int it = 0; it < 4 * n; ++it) {
      fill(seen.begin(), seen.end(), false);
      int lim = hist.size();

      int min_cost = 10;
      for (int i = old_sz; i < lim; ++i) {
        for (auto p : graph[hist[i].node]) {
          if (!avail[p.first]) continue;
          min_cost = min(min_cost, p.second);
        }
      }

      assert(min_cost < 10);
      sol += min_cost + '0';

      for (int i = old_sz; i < lim; ++i) {
        for (auto p : graph[hist[i].node]) {
          if (!avail[p.first]) continue;
          if (min_cost == p.second && !seen[p.first]) {
            seen[p.first] = true;
            hist.push_back(Hist{p.first, i});
          }
        }
      }
      old_sz = lim;
    }

    vector<int> path;
    for (int cur = hist.size() - 1; cur != -1; cur = hist[cur].par) {
      path.push_back(hist[cur].node);
    }
    reverse(path.begin(), path.end());

    int period_starts_at = -1, period_stops_at = -1;
    vector<int> order(n, -1);
    for (int i = 0; i < 4 * n; ++i) {
      if (order[path[i]] != -1) {
        period_starts_at = order[path[i]];
        period_stops_at = i;
        break;
      }
      order[path[i]] = i;
    }

    string non_period = sol.substr(0, period_starts_at);
    string period = sol.substr(period_starts_at,
      period_stops_at - period_starts_at);

    int up = (Out(non_period + period) - Out(non_period)) % kMod;
    int down = Out(string(period.size(), '9') + string(non_period.size(), '0'));
    int ret = 1LL * up * inv(down) % kMod;
    if (ret < 0) ret += kMod;
    cout << "Case #" << tt << ": " << ret << '\n';
  }
  return 0;
}