#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;

struct Lemon {
    Lemon() {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} lemon;

#define lson (k << 1)
#define rson (k << 1 | 1)

const int mod = 7 + 1e9;
// const int mod = 998244353;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
#if LEMON
const int N = 3 + 111;
#else
#define endl '\n'
const int N = 3 + 200;
#endif

int d[N][N], n, q;

void solve() {
    cin >> n >> q;

    vector<PII> a(n);
    vector<array<int, 4>> query(q);

    for (int i = 0; i < n; ++i) {
        a[i].first = i + 1;
        cin >> a[i].second;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> d[i][j];
        }
    }

    for (int i = 0; i < q; ++i) {
        query[i][0] = i;
        cin >> query[i][1] >> query[i][2] >> query[i][3];
    }

    sort(a.begin(), a.end(), [](PII x, PII y) {
        return x.second < y.second;
    });
    sort(query.begin(), query.end(), [](array<int, 4> x, array<int, 4> y) {
        return x[3] < y[3];
    });

    int k = 0;
    for (auto& [id, u, v, w] : query) {
        // cout << id << " " << u << " " << v << " " << w << endl;
        while (k < a.size() && a[k].second <= w) {
            // cout << " " << a[k].first << " " << a[k].second << endl;
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= n; ++j) {
                    d[i][j] = min(d[i][j], d[i][a[k].first] + d[a[k].first][j]);
                }
            }
            ++k;
        }
        w = d[u][v];
    }
    sort(query.begin(), query.end());
    for (auto i : query) {
        cout << i.back() << endl;
    }
    cout << endl;
}

int main() {
    int T;
    cin >> T;
    for (int t = 1; t <= T; ++t) {
        cout << "Case #" << t << ":" << endl;
        solve();
    }
    return 0;
}
/*
1
3 6
1 2 3
0 1 3
1 0 1
3 1 0
1 1 1
1 2 1
1 3 1
1 1 2
1 2 2
1 3 2

*/