#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define Yes cout << "Yes\n"
#define No cout << "No\n"
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define fori(x,y) for(int i=(x);i<=(int)(y);++i)
#define forj(x,y) for(int j=(x);j<=(int)(y);++j)
#define fork(x,y) for(int k=(x);k<=(int)(y);++k)

#define debug(x) cerr << #x << " = " << x << endl

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

ll MOD = 998244353;
ll qpow(ll a,ll p) {ll res=1; while(p) {if (p&1) {res=res*a%MOD;} a=a*a%MOD; p>>=1;} return res;}

int n, q;
const int N = 305;
const int M = 5e5+7;
vector<array<int,3>> query[N];
ll ans[M];

ll g[N][N];
void solve(int l, int r) {
	if (l == r) {
		for (auto [s, t, i]: query[l]) ans[i] = g[s][t];
		return;
	}
	int g2[N][N];
	fori(1, n) forj(1, n) g2[i][j] = g[i][j];
	int mid = l+r>>1;

	fork(l, mid) fori(1, n) forj(1, n) g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
	solve(mid+1, r);
	fori(1, n) forj(1, n) g[i][j] = g2[i][j];

	fork(mid+1, r) fori(1, n) forj(1, n) g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
	solve(l, mid);
	fori(1, n) forj(1, n) g[i][j] = g2[i][j];
}
void solve() {
	cin >> n >> q;
	fori(1, n) forj(1, n) cin >> g[i][j];
	fori(1, q) {
		int s, t, p;
		cin >> s >> t >> p;
		query[p].push_back({s, t, i});
	}
	solve(1, n);
	fori(1, q) cout << ans[i] << endl;
}

signed main() {
	IOS;
	int t = 1;
	// cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}