#include<bits/stdc++.h>
#define pt putchar
using namespace std;
typedef long long ll;
const int N=302;
ll read();
void write(ll x);
int n,q;
ll a[N][N];

ll d[N][N][N];
int L[N],R[N];

void add(int id,int x){
	#define ra(i) int i=(R[id]-1)%n+1;i!=L[id]+1;i=i%n+1
	for(ra(i)){
		d[id][x][i]=a[x][i];
		d[id][i][x]=a[i][x];
		for(ra(j)){
			d[id][x][i]=min(d[id][x][i],a[x][j]+d[id][j][i]);
			d[id][i][x]=min(d[id][i][x],a[j][x]+d[id][i][j]);
		}
	}
	for(ra(i)){
		for(ra(j)){
			d[id][i][j]=min(d[id][i][j],d[id][i][x]+d[id][x][j]); 
		} 
	}
	if(L[id]+1==x){
		L[id]++;
	}
	else if(R[id]-1==x){
		R[id]--;
	}
	/*else{
		printf("%d %d %d %d\n",id,L[id],R[id],x);
		assert(0);
	}*/
}

void solve(int l,int r){
	if(l==r){
		return;
	}
	int mid=(l+r)/2;
	memcpy(d[mid+1],d[l],sizeof d[l]);
	L[mid+1]=L[l];R[mid+1]=R[l];
	for(int i=l;i<=mid;i++){
		add(mid+1,i);
	}
	for(int i=r;i>=mid+1;i--){
		add(l,i);
	}
	solve(l,mid);solve(mid+1,r);
}

int main(){
	n=read();q=read();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			a[i][j]=read();
		}
	}
	memset(d[1],63,sizeof d[1]);
	for(int i=1;i<=n;i++){
		d[1][i][i]=0;
	} 
	L[1]=0;R[1]=n+1;
	solve(1,n);
	while(q--){
		int s=read(),t=read();
		write(d[read()][s][t]);pt('\n');
	}
	return 0;
}

ll read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while('0'<=c&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
void write(ll x){
	if(x<0){
		pt('-');
		x=-x;
	}
	if(x>9){
		write(x/10);
	}
	pt(x%10+'0');
}