#include <iostream>
#include <climits>
#include <fstream>
#define INF 10000
using namespace std;
int a[5000][5000];
int v[5000],d[5000],t[5000],n,x,r[5000],s,T,asd;
ifstream f("distante.in");
ofstream g("distante.out");
void nr()
{

    f>>T;
}
void citire()
{
    int c;

    f>>n>>x>>s;
    for(int i=1;i<=n;i++)
        f>>r[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i==j)
                a[i][j]=0;
            else
                a[i][j]=INF;
    int z,y;
    for(int i=1;i<=x;i++)
    {
        f>>z>>y>>c;
        a[z][y]=c;
    }


}
void alg(int x)
{
    int mi,ok=1,k;

    for(int i=1;i<=n;i++)
    {
        d[i]=a[x][i];
        if((d[i]<INF)&&(d[i]>0))
            t[i]=x;
    }


    v[x]=0;
    t[x]=0;
    while(ok)
    {
        mi=INF;
        for(int i=1;i<=n;i++)
            if((v[i]==0)&&(mi>d[i]))
        {
            mi=d[i];
            k=i;
        }
        if(mi==INF)
            ok=0;
        else
        {
            v[k]=1;
            for(int i=1;i<=n;i++)
                if((v[i]==0) && (d[i]>d[k]+a[k][i]))
            {
                d[i]=d[k]+a[k][i];
                t[i]=k;
            }
        }
    }
}
void afis(int x)
{
    if(x!=0)
    {
        afis(t[x]);
        cout<<x<<" ";
    }
}
int main()
{

        nr();
        for(int i=1;i<=T;i++)
        {citire();

        alg(1);
        int da=1;
        for(int j=1;j<=n;j++)
            {
                if(d[j]!=r[j])
                    da=0;
                if(da==0)
                    break;

            }


        if(da==1)
            g<<"DA \n";
        else
            g<<"NU \n";

        for(int j=1;j<=n;j++)
        {
            v[j]=d[j]=t[j]=0;
        }
        }




    return 0;
}