#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll INF=1e18;

int n,q;
ll a[250][250];
ll b[250][250][250];
ll c[250][250][250];

int main(){
    freopen("hopeicanjump.in","r",stdin);
    freopen("hopeicanjump.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    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++){
            b[0][i][j]=a[i][j];
        }
    }
    for (int k=1;k<=n;++k){
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++){
                ll x=b[k-1][i][j];
                ll y=b[k-1][i][k]+b[k-1][k][j];
                b[k][i][j]=min(x,y);
            }
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            c[n+1][i][j]=a[i][j];
        }
    }
    for (int k=n;k>=1;--k){
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++){
                ll x=c[k+1][i][j];
                ll y=c[k+1][i][k]+c[k+1][k][j];
                c[k][i][j]=min(x,y);
            }
        }
    }
    while (q--){
        ll s,t,p;
        cin>>s>>t>>p;
        ll ans=min(b[p-1][s][t],c[p+1][s][t]);
        ll x=INF,y=INF;
        for (int k=1;k<=n;++k){
            if (k==p) continue;
            x=min(x,b[p-1][s][k]+c[p+1][k][t]);
            y=min(y,c[p+1][s][k]+b[p-1][k][t]);
        }
        ans=min(ans,min(x,y));
        cout<<ans<<'\n';
    }

    return 0;
}