#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
#define INF 5000
using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");
int main()
{
    long m[501][501],t[501],s[501],d[501],i,nr,j,D[501],mini,poz;
    long n,a,b,start,mu;
    long k,c;
    f>>k;
    while (k!=0)
    {
        int ok=1;
        memset(m,0,sizeof(m));
        memset(t,0,sizeof(t));
        memset(s,0,sizeof(s));
        memset(d,0,sizeof(d));
        f>>n>>mu>>start;
        for (i=1;i<=n;i++)
            f>>D[i];
        for (i=1;i<=n;i++)
            for (j=1;j<=n;j++)
                if (i==j)
                    m[i][j]=0;
                else
                    m[i][j]=INF;
        for (i=1;i<=mu;i++)
            {
                f>>a>>b>>c;
                m[a][b]=c;
            }
        for (i=1;i<=n;i++)
        {
            if (m[start][i]!=INF && m[start][i]!=0)
                t[i]=start;
            d[i]=m[start][i];
        }
        s[start]=1;
        for (nr=1;nr<=n-1;nr++)
        {
            mini=INF;
            for (i=1;i<=n;i++)
                if (s[i]==0 && d[i]<mini)
                    {
                        mini=d[i];
                        poz=i;
                    }
            s[poz]=1;
            for (i=1;i<=n;i++)
                if (d[i]>d[poz]+m[poz][i])
                    {
                        d[i]=d[poz]+m[poz][i];
                        t[i]=poz;
                    }

        }
        for (i=1;i<=n;i++)
            if(d[i]!=D[i])
                ok=0;
        if (ok==1)
            g<<"DA"<<'\n';
        else
            g<<"NU"<<'\n';
        k--;


    }
    return 0;
}