#include <bits/stdc++.h>

using namespace std;

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

int t;
int n,m,s;
int dist[50005];
int verif[50005];



struct el
{
    int node,cost;
    bool operator < (const el &A) const{
        return cost > A.cost;
    }
};

priority_queue <el> Q;
vector <el> a[50005];

void Dijkstra(int nod ,int co)
{
    verif[nod]=0;
    while(!Q.empty())
        Q.pop();
    Q.push({nod , co});
    while(!Q.empty())
    {
        int i=Q.top().node;
        int val=Q.top().cost;
        for(int x=0; x<a[i].size() ;++x)
        {
            el V=a[i][x];
            if(verif[V.node]>verif[i]+a[i][x].cost)
            {
                verif[V.node]=verif[i]+a[i][x].cost;
                Q.push({V.node , verif[V.node]});

            }
        }

        Q.pop();
    }
}
int main()
{
    f>>t;
    for(int test=1;test<=t;++test)
    {
        f>>n>>m>>s;
        for(int i=1;i<=n;++i)
        {
            f>>dist[i];
            verif[i]=99999999;
        }

        for(int i=1;i<=m;++i)
        {
            int x , y , val;
            f>>x>>y>>val;
            a[x].push_back({y , val});
            a[y].push_back({x , val});

        }



        Dijkstra(s , 0);
        for(int i=1;i<=n;++i)
            cout<<verif[i]<<" ";
        cout<<"\n";
        int ok=1;
        for(int i=1;i<=n;++i)
            if(verif[i]!=dist[i])
                ok=0;
        if(ok==1)
            g<<"DA"<<"\n";
        else
            g<<"NU"<<"\n";
        for(int i=1;i<=n;++i)
            a[i].clear();
    }
    return 0;
}