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

const int N=311;

int n,q;

long long f[11][N][N];

vector<tuple<int,int,int> >qr[N];

long long ans[511111];

void solve(int l,int r,int d=0)
{
    if(l==r)
    {
        for(auto [x,y,id]:qr[l])
            ans[id]=f[d][x][y];
        return;
    }
    int m=(l+r)>>1;
    for(int k=m+1;k<=r;k++)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                f[d+1][i][j]=f[d][i][j];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                f[d+1][i][j]=min(f[d+1][i][j],f[d][i][k]+f[d][k][j]);
    }
    solve(l,m,d+1);
    for(int k=l;k<=m;k++)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                f[d+1][i][j]=f[d][i][j];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                f[d+1][i][j]=min(f[d][i][j],f[d][i][k]+f[d][k][j]);
    }
    solve(m+1,r,d+1);
}

int main()
{
    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>>f[0][i][j];
    for(int i=1;i<=q;i++)
    {
        int x,y,p;
        cin>>x>>y>>p;
        qr[p].push_back({x,y,i});
    }
    solve(1,n);
    for(int i=1;i<=q;i++)
        cout<<ans[i]<<"\n";
}