// Author : hejinming2012
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define dbg(x) cout << #x " = " << (x) << endl
#define quickio ios::sync_with_stdio(false);
#define quickin cin.tie(0);
#define quickout cout.tie(0);

using namespace std;
inline int read() {
	int now = 0, nev = 1; char c = getchar();
	while(c < '0' || c > '9') { if(c == '-') nev = -1; c = getchar(); }
	while(c >= '0' && c <= '9') { now = (now << 1) + (now << 3) + (c & 15); c = getchar(); }
	return now * nev;
}
void write(int x) {
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}

signed main() {
	quickio
	quickin
    quickout
    int T = read();
	for(int _ = 1; _ <= T; _++) {
		int n = read(), q = read();
		vector <int> r(n + 1);
		for(int i = 1; i <= n; i++)
			r[i] = read();
		vector < vector <int> > d(n + 1, vector <int> (n + 1, 0));
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
				d[i][j] = read();
		vector <int> nodes(n);
		for(int i = 0; i < n; i++)
			nodes[i] = i + 1;
		sort(nodes.begin(), nodes.end(), [&](const int x, const int y) -> bool {
			if(r[x] != r[y]) return r[x] < r[y];
			return x < y;
		});
		vector < vector < vector < pair <int, int> > > > L(n + 1, vector < vector < pair <int, int> > > (n + 1, vector < pair <int, int> > ()));
		for(int u = 1; u <= n; u++)
			for(int v = 1; v <= n; v++)
				L[u][v].emplace_back(0, d[u][v]);
		for(auto &k : nodes) {
			int R = r[k];
			for(int u = 1; u <= n; u++) {
				int D = d[u][k];
				for(int v = 1; v <= n; v++)
					if(D + d[k][v] < d[u][v]) {
						d[u][v] = D + d[k][v];
						L[u][v].emplace_back(R, d[u][v]);
					}
			}
		}
		struct query {
			int u, v, w;
		};
		vector <query> Q(q);
		for(int i = 0; i < q; i++) {
			Q[i].u = read();
			Q[i].v = read();
			Q[i].w = read();
		}
		printf("Case #%lld:\n", _);
		for(int i = 0; i < q; i++) {
			int u = Q[i].u;
			int v = Q[i].v;
			int w = Q[i].w;
			auto &lst = L[u][v];
			int l = 0, r = lst.size();
			while(l < r) {
				int mid = l + r >> 1;
				if(lst[mid].first <= w) l = mid + 1;
				else r = mid;
			}
			if(l == 0) printf("%lld\n", lst[0].second);
			else printf("%lld\n", lst[l - 1].second);
		}
	}
	return 0;
}