#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <string.h>
#define dMAX 50000
#define INF 999999
#define lMAX 500000

using namespace std;

int T;
int n, m, s;
int x, y, c;
vector<pair<int, int> > graf[dMAX + 2];
int dist[dMAX + 2], rdist[dMAX + 2];

/// Buffer
char sir[lMAX];
int idx;

deque<int> myDeque;
int pVerif, newV;

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

void GetInt(int &t) {
    t = 0;
    while (isdigit(sir[idx])) {
        t *= 10;
        t += (int)sir[idx] - '0';
        idx++;
    }
    idx++;
}

bool Corect() {
    int i, j;
    myDeque.clear();
    for (i = 1; i <= dMAX; i++) {
        /// Can improve?
        graf[i].clear();
        dist[i] = 0;
        rdist[i] = INF;
    }
    //fin >> n >> m >> s;
    idx = 0;
    fin.getline(sir, 30);
    GetInt(n);
    GetInt(m);
    GetInt(s);
    idx = 0;
    fin.getline(sir, lMAX);
    for (i = 1; i <= n; i++) {
        GetInt(dist[i]);
    }
    for (i = 1; i <= m; i++) {
        /// Need buffer
        idx = 0;
        //fin >> x >> y >> c;
        fin.getline(sir, 30);
        GetInt(x);
        GetInt(y);
        GetInt(c);
        graf[x].push_back({y, c});
        graf[y].push_back({x, c});
    }

    rdist[s] = 0;
    if (dist[s] != 0) return false;
    myDeque.push_back(s);
    /// Can check while Dijkstra
    while (!myDeque.empty()) {
        pVerif = myDeque.front();
        myDeque.pop_front();
        for (i = 0; i < graf[pVerif].size(); i++) {
            newV = graf[pVerif][i].first;
            c = graf[pVerif][i].second;
            if (rdist[newV] > rdist[pVerif] + c) {
                rdist[newV] = rdist[pVerif] + c;
                myDeque.push_back(newV);
            }
        }
    }
    for (i = 1; i <= n; i++) {
        if (rdist[i] != dist[i]) return false;
    }
    return true;

}

int main()
{
    int i, j;
    fin >> T;
    fin.get();
    for (i = 1; i <= T; i++) {
        Corect() ? fout << "DA\n" : fout << "NU\n";
    }
    return 0;
}