#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
#define DN 50005
#define mp make_pair
#define pb push_back
#define p pair<int,int>
using namespace std;

int n,m,s,cica[DN],dist[DN];
vector< p > list[DN];
priority_queue< p , vector< p > , greater< p > > q;

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

void clear()
{
    for(int j=1;j<=DN-5;++j)
        list[j].clear();
    memset(dist,127,sizeof(dist));
}

void dijkstra()
{
    while(q.size())
    {
        int nod=q.top().first;
        int val=q.top().second;
        q.pop();
        for(unsigned int i=0;i<list[nod].size();++i)
        {
            int next_nod=list[nod][i].first;
            int dista=list[nod][i].second;
            if(val+dista < dist[next_nod] )
            {
                q.push(mp(next_nod,val+dista));
                dist[next_nod]=val+dista;
            }
        }
    }

}

void check()
{
    for(int j=1;j<=n;++j)
        if(cica[j]!=dist[j])
         {
            g<<"NU\n";
            return;
         }
    g<<"DA\n";
}

int main()
{
    int t;
    f>>t;
    for(int i=1;i<=t;++i)
    {
        f>>n>>m>>s;
        clear();

        for(int j=1;j<=n;++j)
            f>>cica[j];

        for(int j=1;j<=m;++j)
        {
            int a,b,c;
            f>>a>>b>>c;
            list[a].pb(mp(b,c));
            list[b].pb(mp(a,c));
        }
        dist[s]=0;
        q.push(mp(s,0));
        dijkstra();
        check();

    }
    return 0;
}