#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N=505;
const ll inf=0x3f3f3f3f3f3f3f3f;
ll dis[N],a[N][N];
int n,q,mk[N];
ll dist(int s,int t,int g){
	for(int i=1;i<=n;i++)dis[i]=inf,mk[i]=0;
	dis[s]=0;
	for(int i=1;i<=n;i++){
		int p=-1;
		for(int j=1;j<=n;j++){
			if(j==g)continue;
			if(!mk[j]&&(p==-1||dis[j]<dis[p]))p=j;
		}
		mk[p]=1;
		for(int j=1;j<=n;j++){
			if(j==g)continue;
			if(!mk[j])dis[j]=min(dis[j],dis[p]+a[p][j]);
		}
	}
	return dis[t];
}
int main(){
	freopen("hopeicanjump.in","r",stdin);
	freopen("hopeicanjump.out","w",stdout);
	scanf("%d %d",&n,&q);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			scanf("%lld",&a[i][j]);
		}
	}
	int s,t,p;
	while(q--){
		scanf("%d %d %d",&s,&t,&p);
		printf("%lld\n",dist(s,t,p));
	}
	return 0;
}