#include<bits/stdc++.h>
#define int long long
#define matsuri pair<int,int>
//const int iris = 1e9+7;
const int iris = 998244353;
using namespace std;

const int N = 300;

vector<vector<int> > arr(N+1, vector<int>(N+1)), dis(N+1, vector<int>(N+1, 1e18));
vector<vector<int> > st(N*4);
vector<vector<tuple<int,int,int> > > qq(N+1);
vector<int> ok;
vector<int> ans;
int n;

void add(int i,int l,int r,int L,int R,int x)
{
	int m=l+(r-l)/2;
	if(L<=l && r<=R)
		st[i].emplace_back(x);
	else if(R<=m)
		add(i*2,l,m,L,R,x);
	else if(L>m)
		add(i*2+1, m+1, r, L, R, x);
	else
	{
		add(i*2,l,m,L,R,x);
		add(i*2+1, m+1, r, L, R, x);
	}
}

void sana(int i,int l,int r)
{
	vector<tuple<int,int,int> > rev;
	
	auto up=[&](int a,int b,int c)
	{
		if(c<dis[a][b])
		{
			rev.emplace_back(a,b,dis[a][b]);
			dis[a][b]=c;
		}
	};
	
	for(int k:st[i])
	{
		for(int i:ok)
		{
			up(k,i,arr[k][i]);
			up(i,k,arr[i][k]);
		}
		for(int i:ok)
		{
			for(int j:ok)
			{
				up(i,k,dis[i][j]+dis[j][k]);
				up(k,i,dis[k][j]+dis[j][i]);
			}
		}
		for(int i:ok)
		{
			for(int j:ok)
			{
				up(i,j,dis[i][k]+dis[k][j]);
			}
		}
		ok.emplace_back(k);
	}
	
	if(l==r)
	{
		for(auto [s,t,id]:qq[l])
			ans[id]=dis[s][t];
	}
	else
	{
		int m=l+(r-l)/2;
		sana(i*2,l,m);
		sana(i*2+1,m+1,r);
	}
	
	/*cout<<" owo "<<i<<' '<<l<<' '<<r<<'\n';
	for(int x:ok)
	{
		cout<<' '<<x;
	}
	cout<<'\n';
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cout<<dis[i][j]<<' ';
		}
		cout<<'\n';
	}*/
	
	reverse(rev.begin(), rev.end());
	for(auto &[a,b,c]:rev)
		dis[a][b]=c;
	for(int &x:st[i])
		ok.pop_back();
}

void solve()
{
	int q;
	cin>>n>>q;
	ans.resize(q);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>arr[i][j];
	for(int i=1;i<=n;i++)
		dis[i][i]=0;
	for(int i=1;i<=n;i++)
	{
		if(i>1)
			add(1,1,n,1,i-1,i);
		if(i<n)
			add(1,1,n,i+1,n,i);
	}
	for(int i=0;i<q;i++)
	{
		int s,t,p;
		cin>>s>>t>>p;
		qq[p].emplace_back(s,t,i);
	}
	sana(1,1,n);
	for(int x:ans)
		cout<<x<<'\n';
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T=1;
	//cin>>T;
	while(T--)
		solve();

	return 0;
}