#include <bits/stdc++.h>
using namespace std;
ifstream f ( "distante.in" );
ofstream g ( "distante.out" );
vector < pair< int ,int > >  v[50005];
set < pair < int , int  >  > s ;
vector < int > date(50005),rasp(50005);
vector < bool >viz(50005);
void parcurgere(int nod)
{   viz[nod]=1;
    for(int i=0;i<v[nod].size();i++)
    {   int vecin=v[nod][i].first;
        int cost=v[nod][i].second;
        if(!viz[vecin])
        {   viz[vecin]=1;
            rasp[vecin]=rasp[nod]+cost;
            s.insert({rasp[vecin],vecin});
        }
        else
        {   if(rasp[nod]+cost<rasp[vecin])
            {   s.erase({rasp[vecin],vecin});
                rasp[vecin]=rasp[nod]+cost;
                s.insert({rasp[vecin],vecin});
            }
        }
    }
}
void rezolva(int n,int m,int p)
{   for(int i=1;i<=n;i++) f>>date[i];
    for(int i=1,a,b,c;i<=m;i++)
    {   f>>a>>b>>c;
        v[a].push_back({b,c});
    }
    rasp[p]=0;
    s.insert({0,p});
    while(!(s.empty()))
    {   int nod=(*s.begin()).second;
        s.erase(s.begin());
        parcurgere(nod);
    }
    bool ok=0;
    for(int i=1;i<=n and !ok;i++)
        if(date[i]!=rasp[i]) ok=1;
    if(!ok) g<< "DA\n";
    else g<< "NU\n";
    for(int i=0;i<=n;i++) v[i].clear();
    date.clear();
    rasp.clear();
    viz.clear();
    return ;
}
int main()
{   int t;
    f>>t;
    while(t--)
    {   int n,m,p;
        f>>n>>m>>p;
        rezolva(n,m,p);
    }
    return 0;
}