#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pli = pair<ll, int>;
const ll inf = 1e18;

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

  int n, q;
  cin >> n >> q;
  vector<vector<vector<ll>>> f(n + 1, vector<vector<ll>>(n + 1, vector<ll>(n + 1, inf)));
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> f[0][i][j];
    }
  }

  vector<vector<tuple<int, int, int>>> Q(n + 1);
  for (int i = 1; i <= q; i++) {
    int s, t, p;
    cin >> s >> t >> p;
    Q[p].push_back({s, t, i});  
  }

  vector<ll> ans(q + 1);
  vector<vector<int>> tr(n * 4 + 1);
  auto add = [&](auto &&self, int u, int l, int r, int ql, int qr, int p) -> void {
    if (ql >= l && qr <= r) {
      tr[u].push_back(p);
      return;
    }
    int m = (l + r) >> 1;
    if (ql <= m) {
      self(self, u << 1, l, m, ql, qr, p);
    }
    if (qr > m) {
      self(self, u << 1 | 1, m + 1, r, ql, qr, p);
    }
  };

  for (int i = 1; i <= n; i++) {
    if (i > 1) {
      add(add, 1, 1, n, 1, i - 1, i);
    }
    if (i < n) {
      add(add, 1, 1, n, i + 1, n, i);
    }
  }

  auto dfs = [&](auto &&self, int u, int l, int r, int d) -> void {
    f[d] = f[d - 1];
    for (auto &p : tr[u]) {
      for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
          f[d][i][j] = min(f[d][i][j], f[d][i][p] + f[d][p][j]);
        }
      }
    }
    if (l == r) {
      for (auto &[s, t, id] : Q[l]) {
        ans[id] = f[d][s][t];
      }
      return;
    }
    int m = (l + r) >> 1;
    self(self, u << 1, l, m, d + 1);
    self(self, u << 1 | 1, m + 1, r, d + 1);
  };
  dfs(dfs, 1, 1, n, 1);

  for (int i = 1; i <= q; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}