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

using namespace std;

vector<long long> Dijkstra(int nod_start,int n,vector<vector<pair<int,int>>> &lista_ad)
{
    //retinem un cost maxim ce nu poate fii atins
    long long infinit=1061109567;

    //vectori ce retine pentru fiecare nod distanta minima de la nodul de start la el, il initializam pe tot cu infinit
    vector<long long> noduri_cost(n+1,infinit);
    noduri_cost[nod_start]=0;

    //vectorul ce retine daca un nod a fost selectat deja sau nu
    vector<int> viz(n+1,0);
    viz[nod_start]=1;

    //in acest heap vom retine perechi de forma (cost,nod) pentru a accesa in O(1) nodul nevizitat cu drumul cel mai scurt
    priority_queue<pair<int,int>> heap;

    //parcurgem toti vecinii nodului de start
        for(int i=0; i<lista_ad[nod_start].size(); i++)
        {
            noduri_cost[lista_ad[nod_start][i].first]=lista_ad[nod_start][i].second;//actualizam drumurile fiecarui vecin
            pair<int,int> cost_nod;//cream pentru fiecare vecin o pereche de forma (cost,nod) si o introducem in heap
            cost_nod.first=-lista_ad[nod_start][i].second;
            cost_nod.second=lista_ad[nod_start][i].first;
            heap.push(cost_nod);
        }
    while(!heap.empty())//cat timp heap-ul are elemente
    {
        //luam primul element din heap(acestea fiind ordonate dupa cel mai mic cost)
        int nod_curent=heap.top().second;
        heap.pop();
        if(viz[nod_curent]==0)//daca nodul curent nu a fost vizitat il selectam
        {
            viz[nod_curent]=1;//nodul devine vizitat
            for(int i=0; i<lista_ad[nod_curent].size(); i++)//parcugem toti vecinii nevizitat ai nodului curent si verificam daca e nevoie de o modifcare a drumului minim
            {
                if(viz[lista_ad[nod_curent][i].first]==0)
                {
                    if(noduri_cost[lista_ad[nod_curent][i].first]>noduri_cost[nod_curent]+lista_ad[nod_curent][i].second)
                    {
                        //in cazul in care drumul minim trebuie modificat introducem o noua pereche in heap
                        noduri_cost[lista_ad[nod_curent][i].first]=noduri_cost[nod_curent]+lista_ad[nod_curent][i].second;
                        pair<int,int> cost_nod;
                        cost_nod.first=-noduri_cost[lista_ad[nod_curent][i].first];
                        cost_nod.second=lista_ad[nod_curent][i].first;
                        heap.push(cost_nod);
                    }
                }
            }
        }

    }
    return noduri_cost;//returnam vectorul de distante minime

}

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

    int nr_total;
    fin>>nr_total;
    for(int k=0;k<nr_total;k++)
    {
        int n,m,s;
        fin>>n>>m>>s;
        cout<<n<<" "<<m<<" "<<s<<"\n";
        vector<long long> dis_minime_initiale(n+1);
        vector<long long> dis_minime_reale(n+1);
        vector<vector<pair<int,int>>> lista_ad(n+1);
        for(int i=1;i<=n;i++)
        {
            fin>>dis_minime_initiale[i];
            cout<<dis_minime_initiale[i]<<" ";
        }
        cout<<"\n";
        for(int i=0;i<m;i++)
        {
            int prim,sec,cost;
            fin>>prim>>sec>>cost;
            cout<<prim<<" "<<sec<<" "<<cost<<"\n";
            lista_ad[prim].push_back(make_pair(sec,cost));
            lista_ad[sec].push_back(make_pair(prim,cost));

        }
        dis_minime_reale=Dijkstra(s,n,lista_ad);
        int ok=1;
        for(int i=1;i<=n;i++)
            if(dis_minime_initiale[i]!=dis_minime_reale[i])
        {
            ok=0;
            break;
        }
        if(ok==1)
            fout<<"DA\n";
        else
            fout<<"NU\n";

        cout<<"\n\n";
    }


    return 0;
}