#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define pob pop_back
#define all(x) begin(x), end(x)
#define SZ(x) ssize(x)
using namespace std;

#ifdef LOCAL
#define HEHE freopen("in.txt", "r", stdin);
#define debug(HEHE...) cerr << #HEHE << " = ", dout(HEHE)
void dout() { cerr << "\n"; }
template<typename T, typename... U>
void dout(T t, U... u) { cerr << t << ' '; dout(u...); }
#else
#define HEHE ios_base::sync_with_stdio(0), cin.tie(0);
#define debug(...) 7122
#endif

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)

#define chmax(a, b) a = (a) > (b) ? (a) : (b)
#define chmin(a, b) a = (a) < (b) ? (a) : (b)

#define int long long

const int inf = 1ll << 60;
int n, q;
vector<vector<int>> dis, pre[305], suf[305];

signed main() {
    HEHE
    cin >> n >> q;
    dis.assign(n + 1, vector<int>(n + 1));
    pre[0].assign(n + 1, vector<int> (n + 1));
    FOR (i, 1, n) FOR (j, 1, n)
        cin >> dis[i][j];
    pre[0] = suf[n + 1] = dis;
    FOR (k, 1, n) {
        pre[k] = pre[k - 1];
        FOR (i, 1, n) FOR (j, 1, n) {
            chmin(pre[k][i][j], pre[k][i][k] + pre[k][k][j]);
        }
    }
    for (int k = n; k >= 1; k--) {
        suf[k] = suf[k + 1];
        FOR (i, 1, n) FOR (j, 1, n) {
            chmin(suf[k][i][j], suf[k][i][k] + suf[k][k][j]);
        }
    }
    while (q--) {
        int s, t, p; cin >> s >> t >> p;
        int ans = inf;
        chmin(ans, pre[p-1][s][t]);
        chmin(ans, suf[p+1][s][t]);
        FOR (i, 1, n) {
            if (i != p)
                chmin(ans, min(pre[p-1][s][i], suf[p+1][s][i]) + min(pre[p-1][i][t], suf[p+1][i][t]));
        }
        cout << ans << '\n';
    }
}