#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define inf 1<<30
#define nmax 50005

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

int nrGrafuri;
int d[nmax];
bool incoada[nmax];

struct compara{
    bool operator()(int a, int b)
    {
        return d[a] > d[b];
    }
};

priority_queue<int, vector<int>, compara> coada;

void dijkstra(int start, int n, vector<pair<int, int> > graf[])
{
    rep(i, 1, n+1)
    {
        d[i] = inf;
        incoada[i] = 0;
    }
    d[start] = 0;
    incoada[start] = 1;
    coada.push(start);
    while(!coada.empty())
    {
        int nod = coada.top();
        coada.pop();
        incoada[nod] = 0;
        rep(i, 0, graf[nod].size())
        {
            int next = graf[nod][i].first;
            int cost = graf[nod][i].second;
            if(d[next] > d[nod] + cost)
            {
                d[next] = d[nod] + cost;
                if(!incoada[next])
                {
                    coada.push(next);
                    incoada[next] = 1;
                }
            }
        }
    }

}

int main()
{
    fin >> nrGrafuri;
    rep(i, 1, nrGrafuri+1)
    {
        int noduri, muchii, start;
        int distante[nmax];
        int da = 1;
        vector<pair<int, int> > graf[nmax];
        fin >> noduri >> muchii >> start;
        rep(j, 1, noduri+1)
            fin >> distante[j];
        rep(j, 1, muchii+1)
        {
            int a, b, c;
            fin >> a >> b >> c;
            graf[a].pb({b, c});
            graf[b].pb({a, c});
        }
        dijkstra(start, noduri, graf);
        rep(i, 1, noduri+1)
            if(distante[i] != d[i])
            {
                fout << "NU\n";
                da = 0;
                break;
            }
        if(da)fout << "DA\n";
    }
    return 0;
}