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

typedef long long ll;
const int N=305;
const ll INF=1e18;
int n,q;
ll a[N][N],ans[N][N][N];

int main()
{
    freopen("hopeicanjump.in","r",stdin);
    freopen("hopeicanjump.out","w",stdout); 
    ios::sync_with_stdio(false);
    cin.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 p=1;p<=n;p++){
        ll d[N][N];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                d[i][j]=a[i][j];
        for(int m=1;m<=n;m++){
            if(m==p)continue;
            for(int i=1;i<=n;i++){
                if(d[i][m]>=INF)continue;
                for(int j=1;j<=n;j++){
                    if(d[m][j]>=INF)continue;
                    if(d[i][j]>d[i][m]+d[m][j])
                        d[i][j]=d[i][m]+d[m][j];
                }
            }
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                ans[i][j][p]=d[i][j];
    }
    while(q--){
        int s,t,p;
        cin>>s>>t>>p;
        cout<<ans[s][t][p]<<endl;
    }
    return 0;
}