#include <bits/stdc++.h>

using namespace std;

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

struct vect{
    int t,c;
    bool operator<(vect other)const
    {
        return this->c < other.c;
    };
}aux;
int n,m,S;

vector<int> dijkstra(vector<vector<vect>> adj)
{
    vector<int> sol(n+2);
    set<vect> s;

    aux.t=1;
    aux.c=0;
    s.insert(aux);
    while(!s.empty())
    {
        vect ts = *s.begin();
        s.erase(s.begin());
        if(sol[ts.t]==0 || sol[ts.t]>ts.c)
        {
            sol[ts.t] = ts.c;
            for(auto it:adj[ts.t])
                if(sol[it.t]==0 || ts.c + it.c < sol[ts.t])
                {
                    aux.t = it.t;
                    aux.c = ts.c + it.c;
                    s.insert(aux);
                }
        }
    }

    sol[S] = 0;
    return sol;
}

void solve(int testcase)
{
    in>>n>>m>>S;
    vector<vector<vect>> v(n+2);
    vector<int> RASP(n+2);
    int a;

    for(int i=1;i<=n;i++)
        in>>RASP[i];

    for(int i=1;i<=m;i++)
    {
        in>>a>>aux.t>>aux.c;
        v[a].push_back(aux);
    }

    vector<int> sol = dijkstra(v);

    int pp=1;
    for(int i=1;pp && i<=n;i++)
        if(RASP[i]!=sol[i])
        {
            out<<"NU\n";
            pp=0;
        }
    if(pp)
        out<<"DA\n";
}

int main()
{
    int t;
    in>>t;
    while(t--)
    {
        solve(t);
    }
    return 0;
}