#include <bits/stdc++.h>
using namespace std;

#define ll long long

ifstream fin("distante.in");
ofstream fout("distante.out");

void dijkstra(vector<vector<pair<int, int>>> &graf, vector<int> &verif, int start, int n){

    vector<int> dist(n+1,INT_MAX);
    dist[start]=0;

 ///distanta, nod;
    set<pair<int, int>> s;
    s.insert({0, start});

    while(!s.empty()){
        ///curent;
        auto [d1, u]= *s.begin();
        s.erase(s.begin());

        for(auto &[v, d2] : graf[u]){
            int d_new=d1+d2;

            if(d_new<dist[v]){

                if(dist[v]!=INT_MAX)
                    s.erase(s.find({dist[v],v}));

                dist[v]=d_new;
                s.insert({dist[v],v});
            }
        }
    }

    int sem=1;
/**
    for(int i=1;i<=n;i++){
        if(dist[i]==INT_MAX)
            dist[i]=0;
        cout<<dist[i]<<" ";
    }
    cout<<endl;
**/

    for(int i=1;i<=n;i++)
        if(dist[i]!=verif[i])
            sem=0;

    fout<<(sem? "DA": "NU")<<endl;

}

void solve(){
    int n, m, start;
    fin>>n>>m>>start;

    vector<int> de_verif(n+1);
    for(int i=1;i<=n;i++)
        fin>>de_verif[i];

    vector<vector<pair<int, int>>> g(n+1);


    for(int i=1;i<=m;i++){
        int a, b, c;
        fin>>a>>b>>c;
        g[a].push_back({b,c});
    }

    dijkstra(g, de_verif, start, n);
    g.clear();

}

int main() {
    ios::sync_with_stdio(false);
    fin.tie(nullptr);

    int t; fin>>t;
    while(t--){
        solve();
    }

    return 0;
}