// Author: Christian Lim
// Date: July 23, 2025

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000;
const int MAXQ = 100;
const int MAXW = 1'000'000;
const int MAXX = 10000;
const int MAXT = 1'000'000'000;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int randint(int lo, int hi) {
  return uniform_int_distribution<int>(lo, hi)(rng);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int c = 10;
  cout << c << "\n";

  while (c--) {
    int n = MAXN;
    int q = MAXQ;

    cout << n << " " << q << "\n";

    // Generate wait times
    for (int i = 1; i <= n; ++i) {
      cout << randint(1, MAXW) << (i == n ? "\n" : " ");
    }

    // Create a random tree
    vector<int> nodes(n);
    iota(nodes.begin(), nodes.end(), 1);
    shuffle(nodes.begin(), nodes.end(), rng);

    for (int i = 1; i < n; ++i) {
      int u = nodes[i];
      int v = nodes[randint(0, i - 1)];
      int x = randint(1, MAXX);
      cout << u << " " << v << " " << x << "\n";
    }

    // Build adjacency list for shortest paths
    vector<vector<pair<int, int>>> adj(n + 1);
    vector<int> wait(n + 1);
    for (int i = 1; i <= n; ++i) wait[i] = randint(1, MAXW);

    for (int i = 1; i < n; ++i) {
      int u = nodes[i];
      int v = nodes[randint(0, i - 1)];
      int x = randint(1, MAXX);
      adj[u].emplace_back(v, x);
      adj[v].emplace_back(u, x);
    }

    // Preprocess with DFS to find shortest distances
    vector<int> depth(n + 1), parent(n + 1);
    vector<long long> dist(n + 1);
    function<void(int, int)> dfs = [&](int u, int p) {
      for (auto [v, w] : adj[u]) {
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        dist[v] = dist[u] + w;
        parent[v] = u;
        dfs(v, u);
      }
    };
    dfs(1, -1);

    // Generate queries
    for (int i = 0; i < q; ++i) {
      int r = randint(1, n);
      int s = randint(1, n);

      // Estimate time by path difference
      long long base_time = abs(dist[r] - dist[s]);
      int extra = randint(0, 2); // 0 = too tight, 1 = exact, 2 = extra
      long long t = base_time;
      if (extra == 0) t = max(0LL, base_time - randint(1, 5));
      if (extra == 1) t = base_time;
      if (extra == 2) t = base_time + randint(1, 100);

      t = min(t, 1LL * MAXT); // cap to MAXT

      cout << r << " " << s << " " << t << "\n";
    }
  }

  return 0;
}

