#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>

using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");
int T,n,m,sursa,a,b,c,k;
int costuri_calc[50010],Tati[3][250010],cost[50010],Start[50010],fr[50010],viz[50010],vec[1000010];
int Solve();
int main()
{
    f>>T;
    for(int TT=1;TT<=T;TT++)
    {
        f>>n>>m>>sursa;
        {
            for(int nn=1;nn<=n;nn++)
                f>>costuri_calc[nn];
                for(int i=1;i<=m;i++)
                {
                    f>>a>>b>>c;
                    k++;
                    Tati[0][k]=b;
                    Tati[1][k]=Start[a];
                    Tati[2][k]=c;
                    Start[a]=k;
                }
                for(int i=2;i<=n;i++)
                    cost[i]=3000;
                vec[1]=1;
            }
        if(Solve()) g<<"DA"<<endl;
        else g<<"NU"<<endl;
    }
}
int Solve ()
{
    int pi=1,ps=1,st,elem;
    while(ps<=pi)
    {
        elem=vec[ps];
        viz[elem]=0;
        st=Start[elem];
        fr[elem]++;
        if(fr[elem]>=n)
        {
            return 0;
            break;
        }
        while(st)
        {
            if(cost[elem]+Tati[2][st]<cost[Tati[0][st]])
            {
                cost[Tati[0][st]]=cost[elem]+Tati[2][st];

                if(viz[Tati[0][st]]==0)
                {
                    viz[Tati[0][st]]=1;
                    vec[++pi]=Tati[0][st];

                }
            }
            st=Tati[1][st];
        }
        ps++;
    }
    for(int i=1;i<=n;i++)
        if(cost[i]!=costuri_calc[i])
            return 0;
    return 1;
}