#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F(i,l,r) for(int i = (l);i <= (r);++i)
#define D(i,r,l) for(int i = (r);i >= (l);--i)
#define vt vector
#define mem(a,x) memset(a,x,sizeof a)
#define mpy(a,x) memcpy(a,x,sizeof a)
#define fi first
#define in inline
#define se second
#define pb push_back
#define all(x) x.begin(),x.end()
#define bug cerr<<"LINE:"<<__LINE__<<" "
mt19937 rd(std::chrono::steady_clock::now().time_since_epoch().count());
constexpr int N = 310,M = 5e5+10;
constexpr ll inf = 1e18,mod = 998244353;


ll read(){
	ll x = 0,f = 1;char c = getchar();
	for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
	for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
	return x * f;
}

template<typename T>void cmax(T &x,T &y){x = x < y ? y : x;}
template<typename T>void cmin(T &x,T &y){x = x < y ? x : y;}

ll n,q;
ll d[N][N],ans[M];
ll l[N][N];

struct node{
	ll s,t,id;
}; 
vector<node>G[N];

vector<pll>e[N];
priority_queue<pll,vector<pll>,greater<pll> >qu; 
bool v[N];
void dij(int s){
	for(int i = 1;i <= n;i++)l[s][i] = inf,v[i] = 0;
	l[s][s] = 0,qu.push({0,s});
	while(!qu.empty()){
		int x = qu.top().se;qu.pop();
		if(v[x])continue;
		v[x] = 1;
		for(auto it : e[x]){
			int y = it.fi;ll z = it.se;
			if(l[s][y] > l[s][x] + z){
				l[s][y] = l[s][x] + z;
				qu.push({l[s][y],y});
			}
		}
	}
}
void mi(int x){
	F(i,1,n)e[i].clear();
	F(i,1,n)
		F(j,1,n)
			if(i != j && i != x && j != x)e[i].pb({j,d[i][j]});
	F(i,1,n)dij(i);
}
int main(){
	freopen("hopeicanjump.in","r",stdin);
	freopen("hopeicanjump.out","w",stdout);
	n = read(),q = read();
	F(i,1,n)
		F(j,1,n)d[i][j] = read();	
	F(i,1,q){
		ll s = read(),t = read(),p = read();
		G[p].pb({s,t,i});
	}
	F(i,1,n){
		mi(i);
		for(auto it : G[i])ans[it.id] = l[it.s][it.t];
	}
	F(i,1,q)printf("%lld\n",ans[i]);
	
	return 0;
}