#include <fstream>
#include <vector>
#include <set>
#include <cstring>
#include <string>
#define inf 9999999


using namespace std;

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

void distante(){
    vector<int> value;
    int T,n,m,sursa;
    bool verif;
    fin>>T;
    for (int i=1; i<=T; i++){
        verif=true;
        fin>>n>>m>>sursa;
       
        value.resize(n+1);
        int Bronzarel[n+1];
        for(int j=1; j<= n; j++)
            fin>>Bronzarel[j];
        value = dijkstra(n,m,sursa);
        for(i=1;i<=n;i++){
            if(value[i] != Bronzarel[i])
                verif=false;
        }
        if(!verif){
            fout<<"NU"<<endl;
            value.clear();
        }
        else{
            fout<<"DA"<<endl;
            value.clear();
        }
    }


}



vector<int> dijkstra(int n, int m, int sursa)
{
    int x, y;//, n, m, sursa;
    int i;
    //fin >> n >> m >> sursa;
    //int value[n + 1]; // in value se retin distantele de la nodul src la restul
    vector<int>value;
    value.resize(n + 1);
    vector<vector<pair<int, int> > > adj;
    adj.resize(n + 1);
    set<pair<int, int> > set_cost_nod; // set_cost_nod retine nodurile inca neprocesate si costul pt a ajunge in ele
    // folosim set pt ca atunci cand vom lua un alt nod vrem sa il luam pe cel cu costul minim
    //  ce se afla la un mom de timp in set_nod_cost, inseamna ca acele noduri nu au fost inca procesate.
    for (int i = 0; i < m; ++i)
    {
        int cost;
        fin >> x >> y >> cost;
        adj[x].push_back(make_pair(y, cost));
    }
    for (i = 1; i <= n; ++i)
    {
        value[i] = inf; 
    }
    value[sursa] = 0;
    set_cost_nod.insert(make_pair(0, sursa)); // cost 0 pt nodul sursa 1
    while (!set_cost_nod.empty())
    {
        int nod = (*set_cost_nod.begin()).second; // luam nodul curent
        set_cost_nod.erase(set_cost_nod.begin()); // pop nod crr si cost
        for (int i = 0; i < adj[nod].size(); ++i)
        {
            int nod_dest = adj[nod][i].first;             // nod_dest = este nodul destinatie de la care plecam din nodul crr("nod")
            int cost_dest = adj[nod][i].second;           // costul muchiei de la nod la nod_dest
            if (value[nod] + cost_dest < value[nod_dest]) // value[nod] retine dist de la nodul src(1) la nodul crr (nod)
            // adugam costul de la nod crr la nod dest sa vedem daca gasim o cale mai "ieftina" din nodul src(1) la nod dest
            {
                if (value[nod_dest] != inf)
                {
                    set_cost_nod.erase(set_cost_nod.find(make_pair(value[nod_dest], nod_dest)));
                    // in cazul in care value[nod_dest] !=inf adica dist din 1 la nod_dest a mai fost actualizata si totusi s-a gasit
                    // un drum mai scurt, vom scoate valoarea veche din set_nod_cost pt a o reactualiza mai jos in value si pt a face push
                    // in set la noua valoare pt nod_dest
                }
                // deci se respecta cond din if
                value[nod_dest] = value[nod] + cost_dest;                  // actualizam noul cost pt nodul dest
                set_cost_nod.insert(make_pair(value[nod_dest], nod_dest)); // inseram in set (costul de a ajung din src la nod_dest, nod dest)
                // la urmatoarele iteratii se va lua nod_dest ca fiind noul nod crr
            }
        }
    }
    // for (int i = 2; i <= n; ++i)
    //     if (value[i] != inf)
    //         fout << value[i] << " ";
    //     else
    //         fout << 0 << " ";
    return value;
}


int main(){

}