#include<iostream>
#include<fstream>
using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");

//n - numarul de linii
//m - numarul de coloane
//T - numarul de grafuri
//c - costul de la x la y

int d[10000];
int T,da;


struct mat{
    long v[1000][1000];
    long dis[1000];
    long n,m,S;
}a[100];

void cit()
{
    f>>T;
    int x,y,z;
    for(int k=1;k<=T;k++)
    {
        f>>a[k].n>>a[k].m>>a[k].S;
        for(int i=1;i<=a[k].n;i++)
            f>>a[k].dis[i];

        for(int i=1;i<=a[k].m;i++)
        {
            f>>x>>y>>z;
            a[k].v[x][y]=z;
        }

        for(int c=1;c<=a[k].n;c++)
            for(int l=1;l<=a[k].n;l++)
                if(l==c) a[k].v[c][l]== 0;
                    else if(a[k].v[c][l]==0) a[k].v[c][l]=10000;

    }
}

void dijkstra (int xo,int l)
{
    int t[1000],v[1000],ok,mn,k;
    for(int i=1;i<=a[l].n;i++)
    {
        v[i]=0;
        t[i]=xo;
        d[i]=a[l].v[xo][i];
    }
    ok = 1;
    v[xo] = 1;
    t[xo] = 0;
    while(ok==1)
    {
        mn = 10000;
        for(int i=1;i<=a[l].n;i++)
            if(v[i]==0 and mn > d[i])
            {
                mn = d[i];
                k = i;
            }
        if(mn!=10000)
        {
            v[k]=1;
            for(int i=1;i<=a[l].n;i++)
            if (v[i] == 0 && d[i] > d[k] + a[l].v[k][i])
            {
                d[i] = d[k] + a[l].v[k][i];
                t[i] = k;
            }
        }
        else ok = 0;
    }
}

int main()
{
    cit();

   // for(int i=1;i<=T;i++)
    //{
        //for(int j=1;j<=a[i].n;j++)
        //{
            //for(int g=1;g<=a[i].n;g++)
               // cout<<a[i].v[j][g]<<" ";
           // cout<<endl;
        //}
        //cout<<endl;
        //for(int k=1;k<=a[i].n;k++)
            //cout<<a[i].dis[k]<<" ";
        //cout<<endl<<endl;
    //}

    for(int i=1;i<=T;i++)
    {
        da=0;
        dijkstra(a[i].S,i);
        for(int j=1;j<=a[i].n and da==0;j++)
            if(a[i].dis[j]!=d[j]) {g<<"NU"<<endl;da=1;}
        if(da==0) g<<"DA"<<endl;
    }
}