#include <fstream>
#include <queue>
#include <vector>
#define INF 0x3f3f3f3f
#define pb push_back
#define mkp make_pair
using namespace std;

vector <pair <int,int> > G[50010];
int nr,k,s,i,n,m,x,y,c,now,D[50010],D2[50010];
bool ok;
struct comp
{
    bool operator () (const int &x, const int &y)
    {
        return ( D[x] > D[y] );
    }
};
priority_queue <int, vector <int>, comp> Q;
ifstream f("distante.in");
ofstream g("distante.out");

int main()
{
    f>>nr;
    for (k=1;k<=nr;k++) {
        f>>n>>m>>s;
        for (i=1; i<=n; i++)
            f>>D2[i];
        x=1;
        while (x<=n) {
            while (!G[x].empty())
                G[x].pop_back();
            x++;
        }
        for (i=1; i<=m; i++)
        {
            f>>x>>y>>c;
            G[x].pb(mkp(y,c));
        }
        for (i=1; i<=n; i++)
            D[i]=INF;
        Q.push(s);
        D[s]=0;
        while (!Q.empty())
        {
            now=Q.top();
            Q.pop();
            for (i=0; i<G[now].size(); i++)
                if (G[now][i].second+D[now]<D[G[now][i].first])
                {
                    D[G[now][i].first]=G[now][i].second+D[now];
                    Q.push(G[now][i].first);
                }
        }
        ok=true;
        for (i=1;i<=m;i++)
            if (D2[i]!=D[i]) ok=false;
        if (ok==false) g<<"NU";
        else g<<"DA";
        g<<"\n";
        }
    return 0;
}