#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_wtih_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, pre[p-1][s][i] + suf[p+1][i][t]);
        }
        cout << ans << '\n';
    }
}

answer.code: In function ‘int main()’:
answer.code:17:24: error: ‘sync_wtih_stdio’ is not a member of ‘std::ios_base’
   17 | #define HEHE ios_base::sync_wtih_stdio(0), cin.tie(0);
      |                        ^~~~~~~~~~~~~~~
answer.code:33:5: note: in expansion of macro ‘HEHE’
   33 |     HEHE
      |     ^~~~