#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#define dMAX 50000
#define INF 999999

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];


deque<int> myDeque;
int pVerif, newV;

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

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;
    for (i = 1; i <= n; i++) fin >> dist[i];
    for (i = 1; i <= m; i++) {
        /// Need buffer
        fin >> x >> y >> c;
        graf[x].push_back({y, c});
        graf[y].push_back({x, c});
    }

    rdist[s] = 0;
    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;
    for (i = 1; i <= T; i++) {
        Corect() ? fout << "DA\n" : fout << "NU\n";
    }
    return 0;
}