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

#define ll long long
int n,q;
ll e[305][305];
ll dis[305];
bool vis[305];
#define inf 1e18


void dij(int s,int t,int p){
	for(int i=1;i<=n;i++){
		dis[i]=inf;
		vis[i]=false;
	}
	dis[s]=0;
	dis[0]=inf;
	vis[p]=true;
	while(true){
		int u=0;
		for(int i=1;i<=n;i++){
			if(i==p){
				continue;
			}
			if(!vis[i]&&dis[u]>dis[i]){
				u=i;
			}
		}
		if(u==0){
			break;
		}
		vis[u]=true;
		for(int i=1;i<=n;i++){
			if(i==p){
				continue;
			}
			if(dis[i]>dis[u]+e[u][i]){
				dis[i]=dis[u]+e[u][i];
			}
		}
	} 
}

int main(){
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	freopen("hopeicanjump.in","r",stdin);
	freopen("hopeicanjump.out","w",stdout);	
	
	cin>>n>>q;
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>e[i][j];
		}
	}
	
	
	while(q--){
		int s,t,p;
		cin>>s>>t>>p;
		dij(s,t,p);
		cout<<dis[t]<<"\n";
	}
	
	
	
	
	
	return 0;
}