#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=5e18+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]={a[i][j], 1};
    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};
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++) if (i!=k){
            for(int j=1;j<=n;j++) if (j!=i&&j!=k){
                if (dp1[i][j].F>dp1[i][k].F+dp1[k][j].F){
                    dp2[i][j]=dp1[i][j].F;
                    dp1[i][j]={dp1[i][k].F+dp1[k][j].F, dp1[i][k].S*dp1[k][j].S};
                    dp2[i][j]=min({dp2[i][j], dp1[i][k].F+dp2[k][j], dp2[i][k]+dp1[k][j].F});
                }else if (dp1[i][j].F==dp1[i][k].F+dp1[j][k].F){
                    dp1[i][j].S+=dp1[i][k].S*dp1[k][j].S;
                    dp2[i][j]=min({dp2[i][j], dp1[i][k].F+dp2[k][j], dp2[i][k]+dp1[k][j].F});
                }else{
                    dp2[i][j]=min(dp2[i][j], dp1[i][k].F+dp1[k][j].F);
                }
            }
        }
    }
    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();
}