#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define lson root<<1,l,midd

#define rson root<<<1|1,midd+1,r

#define pb push_back

const int M=;

const int inf=0x3f3f3f3f;

int a[M],b[M],dp[M][M][M];

bool cmp(int x,int y){

    return a[x]<a[y];

}

int main(){

    int t;

    scanf("%d",&t);

    for(int l=;l<=t;l++){

        int n,m;

        scanf("%d%d",&n,&m);

        memset(dp,inf,sizeof(dp));

        for(int i=;i<=n;i++)

            scanf("%d",&a[i]),b[i]=i;

        sort(b+,b++n,cmp);

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

                scanf("%d",&dp[][i][j]);

        for(int k=;k<=n;k++){

            int now=b[k];

            for(int i=;i<=n;i++)

                for(int j=;j<=n;j++)

                    dp[k][i][j]=min(dp[k-][i][j],dp[k-][i][now]+dp[k-][now][j]);

        }

        printf("Case #%d:\n",l);

        while(m--){

            int u,v,up;

            scanf("%d%d%d",&u,&v,&up);

            int mubiao=;

            for(int i=;i<=n;i++){

                if(a[b[i]]>up)

                    break;

                mubiao++;

            }

            printf("%d\n",dp[mubiao][u][v]);

        }

    }

    return ;

}