#include<bits/stdc++.h>
using namespace std;
int const N=302;
int g[N][N],d[N][N];
int main()
{
	freopen("hopeicanjump.in","r",stdin);
	freopen("hopeicanjump.out","w",stdout);
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) cin>>g[i][j];
	}
	while(q--){
		int s,t,p;
		cin>>s>>t>>p;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++) d[i][j]=g[i][j];
		}
		for(int k=1;k<=n;k++){
			if(k==p) continue;
			for(int i=1;i<=n;i++){
				if(i==p||k==i) continue;
				for(int j=1;j<=n;j++){
					if(j==p||i==j || j==k) continue;
					d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
				}
			}
		}
		cout<<d[s][t]<<endl;
	}
	return 0;
}