//https://www.infoarena.ro/problema/distante

#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
///distante
/**
t- nr grafu
n noduri
m muchii
s nod sursa
dn++ cost calc de future coleg de camera la nebuni
dm++ nod nod cost
d[] dement calc
*/
#define pb push_back
#define cin in
#define cout out
int cost[50001],d[50001],n,m,s,t;
bool masca[50001];

struct compara
{
    bool operator()(int x, int y)
    {
        return cost[x] > cost[y];
    }
};
priority_queue<int, vector<int>, compara> q;

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

int krusadi(int x, vector < pair<int,int> >v[])
{
    q.push(x);
    int nod;
    while (!q.empty())
    {
        nod=q.top();
        q.pop();

        masca[nod]=false;
        for (auto coleg:v[nod])
        {
            int colegu=coleg.first;
            int chirie=coleg.second;
            if (cost[colegu]==0 || cost[colegu] > cost[nod]+chirie)
            {
                cost[colegu] = cost[nod] + chirie;
                if (masca[colegu]==false)
                {
                    masca[colegu]=true;
                    q.push(colegu);
                    
                }

            }
        }
    }
}
/*
void afis()
{
    for (int i=0;i<n;i++)
    {
        cout<<i<<": ";
        for (auto j:v[i])
        cout<<j.first<<" "<<j.second<<", ";
        cout<<'\n';
    }
}**/
bool cit()
{
    int a,b,ca;
    cin >> n>> m >> s;
    vector < pair<int,int> >v[50001];

    for (int i=1;i<=n;i++)
        cin>>d[i];
    for (int i=0;i<m;i++)
    {
        cin>> a >> b >> ca;
        v[a].pb(make_pair(b,ca));
        v[b].pb(make_pair(a,ca));
    }
    krusadi(s,v);
    for(int i = 0 ; i < n ; i ++){
        cout << cost[i]<<" ";
    }cout <<endl;
    
    bool aw=true;
    for (int i=1;i<=n;i++)
        if (d[i]!=cost[i])
            aw=false;
    return aw;
}

int main()
{
    cin>>t;
    for (int e=0; e<t; t--)
    {
        bool res = cit();
        if(res){
            cout << "DA" <<'\n';
        }else{
            cout << "NU" <<'\n';
        }
        /*for (int i=1;i<=n;i++)
            cout<<i<<": "<<cost[i]<<" ";
        */
    }
    return 0;
}