#include <iostream>
#include <bits/stdc++.h>

using namespace std;

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


const int inf = 1000000005;
vector<pair<int,int> > G[50001];
priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq;
int n, m, t, x, y, c, svizitate[50001], distanta[50001], bronzarel[50001], continua=0

void citire()
{
    f>>n>>m>>s;
        for(int j=1;j<=n;j++)
            f>>bronzarel[j];

        for(int i=1;i<=m;i++)
        {
            f>>x>>y>>c;
            G[x].push_back(make_pair(c,y));
            G[y].push_back(make_pair(c,x));
        }
}
void dijsktra(int s)
{
    for(int i=1;i<=n;i++)
    {distanta[i]=inf;}

    distanta[s]=0;
    pq.push(make_pair(distanta[s],s));
    while(!pq.empty())
    {
        int curent=pq.top().second;
        pq.pop();
            for(size_t i=0;i<G[curent].size();i++)
            {
                int vecin = G[curent][i].second;
                int cost = G[curent][i].first;
                if(distanta[curent] + cost < distanta[vecin])
                {
                    distanta[vecin]=distanta[curent]+cost;
                    if(!vizitate[vecin])
                        pq.push(make_pair(distanta[vecin],vecin));
                }
            }
            vizitate[curent]=1;

    }
}

void afisare(){
    for(int i=1;i<=n;i++)
        {
            if(bronzarel[i]!=distanta[i])
            {
                continua=1;
                g<<"NU"<<'\n';
                break;

            }
        }
        if(continua==0)
            g<<"DA"<<'\n';
}

void reinitializare(){
    for(int i=1;i<=n;i++)
   {
      G[i].clear();
      vizitate[i]=0;
      distanta[n]=inf;
   }
   continua=0;
   t--;

}
int main()
{
    f>>t;
    while(t)
    {   citire();
        dijsktra(s);
        afisare();
        reinitializare();
    }
    return 0;
}