#include <bits/stdc++.h>
#define NMAX 500001
#define mod 104659
using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");

vector<vector<pair<int,int>>>graf;

priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
vector<long long>cost(NMAX,1LL<<60);
bitset<NMAX>vis;

void dijkstra(int startnode) {
    cost[startnode] = 0;
    q.push({0, startnode});

    while (!q.empty()) {
        pair<long long, int> k = q.top();
        q.pop();

        if (vis[k.second]) continue;
        vis[k.second] = 1;

        for (int i = 0; i < (int)graf[k.second].size(); ++i) {
            int nxt = graf[k.second][i].first;
            int val = graf[k.second][i].second;

            if (k.first + val < cost[nxt]) {
                cost[nxt] = k.first + val;
                q.push({cost[nxt], nxt});
            }
        }
    }
}

void ver(int n, vector<int>bf){
    for(int i=1; i<=n; ++i)
        if(bf[i]!=cost[i])
    {
        g<<"NU"<<'\n';
        return;
    }
    g<<"DA"<<'\n';
}
int main()
{
    int n,m,t,start;
    f>>t;
    for(int i=1; i<=t; ++i){
        f>>n>>m>>start;
        vector<int>bf(n+1);
        graf.resize(n+1);
        for(int i=1; i<=n; ++i)
            f>>bf[i];
    for(int i=1; i<=m; ++i){
        int a,b,c;
        f>>a>>b>>c;
        graf[a].push_back({b,c});
        graf[b].push_back({a,c});
    }
    dijkstra(start);
    ver(n,bf);
    vis.reset();

    }
    return 0;
}