#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#include <map>
using namespace std;
const int INF=1e9;
typedef struct
{
    int a,b,c;
}muchie;
struct cmp {
    bool operator()(const pair<int,int> &left, const pair<int,int> &right) {
        return left.second < right.second;
    }
};
int* Dijkstra(vector <pair<int,int>> v,int N,int M,int nod_start)
{
//    sort(0,N,cmp);
    int *d,i,*tata,counter=N;
    d=new int[N];
    for(i=1;i<=N;i++)
    {
        d[i]=INF;
        tata[i]=0;
    }
    d[nod_start]=0;
    int index=1,nod;
    while(index!=N+1)
    {
        int nod;
        if(index!=nod_start)
        {
            nod=index;
        }
        index++;
        for(int j=0;j<v[nod].size();j++)
        {
            if(d[nod]+v[nod].second<d[v[nod].first])
            {
                d[v[nod].first]=d[nod]+v[nod].second;
                tata[v[nod].first]=nod;
            }
        }
        counter--;
    }
    return d;
}
int comparare(int a[],int b[],int N)
{
    for(int i=1;i<=N;i++)
    {
        if(a[i]!=b[i])
        {
            return 0;
        }
    }
    return 1;
}
int main()
{

    ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");
    int index,T;
    fin>>T;
    for(index=1;index<=T;index++)
    {
    vector < pair<int,int> > v[50001];
    cout<<v[0].first<<' '<<v[0].second;
    int N,M,S,i,j;
    fin>>N>>M>>S;
    int *dist,*new_dist;
    dist=new int[N];
    new_dist=new int[N];
    for(i=1;i<=N;i++)
    {
        fin>>dist[i];
    }
    for(i=1;i<=M;i++)
    {
        muchie x;
        fin>>x.a>>x.b>>x.c;
        v[x.a].push_back(make_pair(x.b,x.c));
    }
    new_dist=Dijkstra(v,N,M,S);
    if(comparare(dist,new_dist,N)==1)
    {
        fout<<"DA";
    }
    else
    {
        fout<<"NU";
    }
    fout<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}