#include <fstream>
#include <vector>

using namespace std;

ifstream f("distante.in");
ofstream g("distante.out");


struct abc
{
    int unde;
    int cost;
};

int i,x;
int distanta[50005],solutii[50005];
abc aux;

void solve()
{
    vector<abc> vecini[50005];

    bool a,bun=true;
    int j,i,n,m,x,y,c,s;
    f>>n>>m>>s;
    for(i=1; i<=n; i++)
    f>>solutii[i];
    for(i=0; i<m; i++)
    {
        f>>x>>y>>c;
        aux.unde=y;
        aux.cost=c;
        vecini[x].push_back(aux);
    }
    for(i=1; i<=n; i++)
    {
        distanta[i]=1000000;
    }
    distanta[s]=0;
    a=true;
    while(a)
    {
        a=false;
        for(i=1; i<=n; i++)
            for(j=0; j<vecini[i].size(); j++)
                if(distanta[i]+vecini[i][j].cost<distanta[vecini[i][j].unde])
                {
                    distanta[vecini[i][j].unde]=distanta[i]+vecini[i][j].cost;
                    a=true;
                }
    }
    for (i = 1; i <= n; i++)
    {
        if (distanta[i] == 1000000)
        {
            if(solutii[i]!=0) bun=false;
        }
        else if(solutii[i]!=distanta[i]) bun=false;
    }
    if(bun) g<<"DA"<<'\n';
    else g<<"NU"<<'\n';
}

int main()
{
    f>>x;
    for(i=0; i<x; i++)
        solve();
    return 0;
}