#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];

void solve()
{
    vector<abc> vecini[50005];
    abc aux;
    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 = 2; 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';
        g<<"NU"<<'\n';
}

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