#include <fstream>
#include <set>
#include <vector>
#define DIM 50060
#define INF 1000000000
using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");
int T,n,m,st,D[DIM],A[DIM];
bool viz[DIM];

vector<pair<long long,int> > L[DIM];
set<pair<long long,int> > S;

int main(void){
    register int i,nod,j,x,y,c,ok;
    pair<long long,int> p,q;
    long long val;

    f>>T;
    for(;T>0;T--){
        f>>n>>m>>st;
        for(i=1;i<=n;i++)
            f>>A[i],D[i]=INF,viz[i]=false;
        D[st]=0;

        for(i=1;i<=m;i++){
            f>>x>>y>>c;
            L[x].push_back(make_pair(c,y));
            L[y].push_back(make_pair(c,x));
        }

        ok=1;
        S.insert(make_pair(0,1));
        while(!S.empty()){
            //alegem minimul curent
            val=S.begin()->first;
            nod=S.begin()->second;
            S.erase(S.begin());
            if(viz[nod])
                continue;
            for(i=0;i<L[nod].size();i++){
                if(D[L[nod][i].second]>D[nod]+L[nod][i].first){
                    D[L[nod][i].second]=D[nod]+L[nod][i].first;
                    S.insert(make_pair(D[L[nod][i].second],L[nod][i].second));
                }
            }
            viz[nod]=true;
        }
        for(i=1;i<=n;i++)
            if(A[i]!=D[i]){
                ok=0;
                break;
            }
        if(!ok){
            g<<"NU\n";
            continue;
        }
        g<<"DA\n";
    }

    f.close();
    g.close();
    return 0;
}