#include <stdio.h>
#include <fstream>
#include<limits.h>
#include <iostream>
#include <vector>
#include <queue>
#define NMAX 50005
using namespace std;

struct edge
{
    int nod;
    int cost;
    edge *next;
};

void add(edge **a, int cost, int from,int where)
{
    edge * p = new edge();
    p->cost = cost;
    p->nod = where;
    p->next = a[from];
    a[from] = p;

    edge*q = new edge();
    q->cost = cost;
    q->nod = from;
    q->next = a[where];
    a[where] = q;
}

class Compare
{
    public:
        bool operator() (pair<int, int> a, pair<int, int> b) {
        return b.second < a.second;
    }
};

int djikstra(int x0, int *d, int *dist,int n, edge **a)
{
    for(int i = 1; i <=n; ++i)
    {
        d[i] = INT_MAX;
    }

    priority_queue<pair<int, int>, vector< pair<int,int> >, Compare> q;

    d[x0] = 0;
    q.push(make_pair(x0,0));

    int viz[n+1];
    for(int i = 0;i <= n;i++)
        viz[i] =0;

    for(int i=1;i<=n;i++)
    {
        pair<int, int> min = q.top();
        q.pop();

        edge *p = a[min.first];
        while(p!= NULL)
        {
            if(d[p->nod] == INT_MAX && d[p->nod] > min.second + p->cost)
            {
                d[p->nod] = min.second + p->cost;
                q.push(make_pair(p->nod,d[p->nod]));
            }
            p = p->next;
        }
    }



    for(int i = 1; i<= n ;i++)
    {
        cout<<d[i] << " ";
        //if(d[i] != dist[i])
            //return 0;

    }
    cout<<"\n";
    return 1;
}

int main(void)
{
    int t;
    int n,m,s;
    std::ifstream f("distante.in");
    f>>t;
    std::ofstream g("distante.out");

    for(int j = 0; j<t;++j)
    {
        f>>n>>m>>s;
        int dist[NMAX];

        for(int i = 1;i <= n; ++i)
        {
            f>>dist[i];
        }
        edge *a[NMAX];
        for(int i = 0;i<=n;i++)
        {
            a[i] = NULL;
        }

        for(int i = 1;i<=m; ++i)
        {
            int x,y,z;
            f>>x>>y>>z;
            add(a,z,x,y);
        }
        int d[NMAX];

        if( djikstra(s ,d,dist,n,a) )
            g<<"DA\n";
        else
            g<<"NU\n";


    }
    return 0;
}