#include <fstream>
#include <bits/stdc++.h>

#define NMAX 50001
#define INFINIT 1000000005

using namespace std;

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

struct muchie {
    int destinatie, cost;

    muchie(int x, int y) : destinatie(x), cost(y) {};
};

vector<vector<muchie>> listaDeAdiacenta;
int nrNoduri, nrMuchii, nrGrafuri, s, vizitat[50001], distante[50001], distanteDate[50001];
bool ok = true;

void reinitializareGraf() {
    for (int i = 1; i <= nrNoduri; i++) {
        listaDeAdiacenta[i].clear();
        vizitat[i] = 0;
        distante[nrNoduri] = INFINIT;
    }
    ok = true;
}

void afisare() {
    for (int i = 1; i <= nrNoduri; i++) {
        if (distanteDate[i] != distante[i]) {
            ok = false;
            fout << "NU" << '\n';
            break;
        }
    }
    if (ok)
        fout << "DA" << '\n';
}

void dijsktra(int nodPlecare) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap; // {cost, nodDestinatie}
    for (int i = 1; i <= nrNoduri; i++)
        distante[i] = INFINIT;
    minHeap.push(make_pair(0, 1)); // introduc in minHeap prima data costul de la nodStart, care este 0 si nodulStart
    distante[1] = 0; // distante pana la nodulStart este 0

    while (!minHeap.empty()) {
        int nod = minHeap.top().second; // iau nodul cel mai apropiat din minHeap
        minHeap.pop(); // il scot din minHeap
        if (!vizitat[nod]) { // daca nu am verificat inca nodul
            vizitat[nod] = 1; // il marchez ca fiind verificat
            for (auto &i: listaDeAdiacenta[nod]) // iau toate nodurile adiacente cu el
                if (distante[nod] + i.cost < distante[i.destinatie]) {
                    // daca distante pana la nodul in care sunt + costul pana la nodul adiacent cu el
                    // este mai mic decat distante pana nodul adiacent cu el
                    // atunci actualizez distante ca fiind:
                    // distante pana nodul meu + costul pana nodul adiacent cu el
                    distante[i.destinatie] = distante[nod] + i.cost;
                    minHeap.push(make_pair(distante[i.destinatie], i.destinatie));
                    // introduc in minHeap distante actualizata pana la nodul adiacent cu nodul meu,
                    // si nodul adiacent cu mine
                }
        }
    }
}

void citireGraf() {
    fin >> nrNoduri >> nrMuchii >> s;
    for (int j = 1; j <= nrNoduri; j++)
        fin >> distanteDate[j];

    for (int i = 1; i <= nrMuchii; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        listaDeAdiacenta[x].push_back(muchie(y, c));
        listaDeAdiacenta[y].push_back(muchie(x, c));
    }
}

int main() {
    listaDeAdiacenta.resize(NMAX, vector<muchie>());
    fin >> nrGrafuri;
    for (int i = 1; i <= nrGrafuri; i++) {
        citireGraf();
        dijsktra(s);
        afisare();
        reinitializareGraf();
    }

    fin.close();
    fout.close();
    return 0;
}