#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <utility>
using namespace std;
typedef long long ll;
const int N = 302;
const ll inf = 0x3f3f3f3f3f3f3f3f;
ll a[N][N];
int head[N], nxt[N * N], to[N * N];
ll vl[N * N], num;
void add(int u, int v, ll w) {
    num++;
    to[num] = v;
    vl[num] = w;
    nxt[num] = head[u];
    head[u] = num;
}
ll dis[N];
bool vis[N];
void dij(int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    priority_queue<pair<ll, int>> p;
    p.push(make_pair(0, s));
    while (!p.empty()) {
        int u = p.top().second;
        p.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = head[u]; i; i = nxt[i]) {
            int v = to[i];
            if (dis[v] > dis[u] + vl[i]) {
                dis[v] = dis[u] + vl[i];
                p.push(make_pair(-dis[v], v));
            }
        }
    }
}
int main() {
    freopen("hopeicanjump.in", "r", stdin);
    freopen("hopeicanjump.out", "w", stdout);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    while (q--) {
        int s, t, p;
        cin >> s >> t >> p;
        num = 1;
        memset(head, 0, sizeof(head));
        for (int i = 1; i <= n; i++) {
            if (i == p) continue;
            for (int j = 1; j <= n; j++) {
                if (i == j || j == p) continue;
                add(i, j, a[i][j]);
            }
        }
        dij(s);
        cout << dis[t] << endl;
    }
    return 0;
}