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

const int inf = 0x3f3f3f3f;
#define nmax 50005
#define mmax 100005
#define cmax 1005

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


vector <pair<int,int>> la[nmax];
int dist[nmax];
set <pair<int,int>> s;

void dijkstra(int ns){
    // Se seteaza vectorul de distante minime cu inf
    memset(dist, inf, sizeof(dist));
    dist[ns]=0;

    // Se adauga nodul de start in set
    s.insert(make_pair(dist[ns],ns));

    while(!s.empty()){
        int nod = s.begin()->second;
        int dmin = s.begin()->first;
        s.erase(s.begin());
        // Pentru fiecare vecin al nodului curent se actualizeaza distanta minima
        for(int k=0; k<la[nod].size(); k++){
            int nod2 = la[nod][k].first;
            int cost = la[nod][k].second;
            if(dmin+cost< dist[nod2]){
                if(dist[nod2] != inf){
                    s.erase(s.find(make_pair(dist[nod2], nod2)));
                }
                dist[nod2] = dmin+cost;
                s.insert(make_pair(dist[nod2], nod2));
            }
        }
    }
}

int main()
{
    int t,n,m,s,x,y,c,d[nmax];

    f>>t;

    for(int i=0; i<t; i++){
        // Citirea datelor
        f>>n>>m>>s;

        for(int j=1; j<=n; j++){
            f>>d[j];
        }

        for(int k=0; k<m; k++){
            f>>x>>y>>c;
            la[x].push_back(make_pair(y,c));
        }

        // In vectorul dist se obtine solutia dupa apelarea functiei dijkstra()
        dijkstra(s);

        // Se verifica daca solutia obtinuta este aceeasi cu solutia citita din fisier
        int ok=1;
        for(int l=1; l<=n; l++){
            if(dist[l]==inf && d[l]!=0) ok=0;
            else if(dist[l]!=d[l]) ok=0;
        }

        if(ok) cout<<"DA"<<endl;
        else cout<<"NU"<<endl;

        // Se elibereaza la[nmax] pentru citirea urmatorului graf
        for(int h=1; h<=n; h++){
            la[h].clear();
        }

    }


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