#include <bits/stdc++.h>
#define Dmax 50005
#define inf 0x3F3F3F3F
using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");


int main()
{
    int T;
    f>>T;
    for(int p = 1; p <= T; p++)
    {
        if(p!=1)
            g<<"\n";
        int n,m,start;
        f>>n>>m>>start;
        int D[Dmax];
        for(int i = 1; i <= n; i++)
            f>>D[i];
        vector<pair<int,int> >G[Dmax];
        for(int i = 1; i <= m; i++)
        {
            int x,y,z;
            f>>x>>y>>z;
            G[x].push_back({y,z});
            G[y].push_back({x,z});
        }
        int D2[Dmax];
        for(int i = 1; i <= n; i++)
            D2[i] = inf;
        D2[start] = 0;
        priority_queue<pair<int,int> >Q;
        Q.push({0,start});
        while(!Q.empty())
        {
            int x = Q.top().first;
            int y = Q.top().second;
            Q.pop();
            x = -x;
            if(x > D2[y])
                continue;
            for(vector<pair<int,int> >::iterator it = G[y].begin(); it < G[y].end(); it++)
            {
                int Vecin = it->first;
                int Cost = it->second;
                if(D2[Vecin] > D2[y] + Cost)
                {
                    D2[Vecin] = D2[y] + Cost;
                    Q.push({-D2[Vecin],Vecin});
                }
            }
        }
        bool ok = true;
        for(int i = 1; i <= n && ok; i++)
            if(D[i]!=D2[i])
        {
            g<<"NU";
            ok = false;
        }
        if(ok)
            g<<"DA";

    }



    return 0;
}