#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 205;

int adj[N][N];
int risk[N];
int n;

int dijkstra(int u, int v, int thresh){
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    vi dis(N, 1e9);
    pq.emplace(u, 0);

    while(!pq.empty()){
        u = pq.top().first;
        int d = pq.top().second; pq.pop();

        if(risk[u] > thresh || d > dis[u]) continue;

        dis[u] = d;

        for(int i = 1; i <= n; i++){
            if(adj[u][i] && risk[i] <= thresh && dis[i] > dis[u] + adj[u][i]){
                pq.emplace(i, dis[u] + adj[u][i]);
            }
        }
    }
    return dis[v];
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    int t;
    cin >> t;

    for(int idx = 1; idx <= t; idx++){
        int q;
        cin >> n >> q;

        for(int i = 1; i <= n; i++){
            cin >> risk[i];
        }

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                cin >> adj[i][j];
            }
        }

        int x, y, w;
        for(int i = 0; i < q; i++){
            cin >> x >> y >> w;
            cout << dijkstra(x, y, w) << "\n";
        }
    }

}