#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
typedef long long loli;
typedef pair<int, int> pii;
typedef pair<loli, loli> pll;
#define F first
#define S second

const int N=305;
const loli LINF=5e16+7;
loli a[N][N];
pll dp1[N][N];
loli dp2[N][N];

void _solve(){
    int n, q;
    cin >> n >> q;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin >> a[i][j];
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dp1[i][j]={LINF, 0};
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dp2[i][j]=LINF;
    for(int i=1;i<=n;i++) dp1[i][i]={0, 1};
    priority_queue<pll, vector<pll>, greater<pll>> pq;
    for(int i=1;i<=n;i++){
        pq.push({0, i});
        while(!pq.empty()){
            auto [dis, x]=pq.top();
            pq.pop();
            if (dis!=dp1[i][x].F) continue;
            for(int e=1;e<=n;e++) if (x!=e){
                if (dp1[i][e].F>(dp1[i][x].F+a[x][e])){
                    dp2[i][e]=dp1[i][e].F;
                    dp1[i][e]={dp1[i][x].F+a[x][e], dp1[i][x].S};
                    pq.push({dp1[i][e].F, e});
                }else if (dp1[i][e].F==(dp1[i][x].F+a[x][e])){
                    dp1[i][e].S+=dp1[i][x].S;
                }else{
                    dp2[i][e]=min(dp2[i][e], (dp1[i][x].F+a[x][e]));
                }
            }
        }
    }
    while(q--){
        int s, t, p;
        cin >> s >> t >> p;
        if ((dp1[s][t].F==dp1[s][p].F+dp1[p][t].F)&&(dp1[s][t].S==dp1[s][p].S*dp1[p][t].S)){
            cout << dp2[s][t] << '\n';
        }else{
            cout << dp1[s][t].F << '\n';
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _t=1;
    //cin >> _t;
    while(_t--) _solve();
}