#include <bits/stdc++.h>
#define N 50004
#define inf 1e9

using namespace std;

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

int D[N], S[N];
int task;
int d[N];
int n, m, z;
vector< pair< int, int > > g[N];

struct cmp
{
    bool operator()(int a, int b)
    {
        return D[a] > D[b];
    }
};

priority_queue< int, vector<int>, cmp > q;

void Citire()
{
    int i;
    int x, y, c;
    fin >> n >> m >> z;
    for( i=1; i<=n; i++ )
        fin >> d[i];
    for( i=1; i<=m; i++ )
    {
        fin >> x >> y >> c;
        g[x].push_back( make_pair(y, c) );
        g[y].push_back( make_pair(x, c) );
    }
}

void Dijkstra( int x )
{
    int i;
    for( i=1; i<=n; i++ )
        D[i] = inf, S[i] = 0;
    D[x] = 0;
    q.emplace( x );
    S[x] = 1;
    while( !q.empty() )
    {
        int nod = q.top();
        int c = D[nod];
        q.pop();
        S[nod] = 0;
        for( auto y : g[nod] )
        {
            if( y.second + c < D[y.first] )
            {
                D[y.first] = c + y.second;
                if( !S[y.first] )
                {
                    q.emplace( y.first );
                    S[y.first] = 1;
                }
            }
        }
    }
}

void Rezolvare()
{
    int i;
    bool ok = 1;
    for( i=1; i<=n; i++ )
    {
        if( D[i] != d[i] ) ok = 0;
        cout << D[i] << " ";
    }
    if( ok ) fout << "DA";
    else fout << "NU";
}

int main()
{
    fin >> task;
    while(task--)
    {
        Citire();
        Dijkstra(z);
        Rezolvare();
        fout << "\n";
        cout << "\n";
        for( int i=1; i<=n; i++ )
            g[i].clear();
    }
    return 0;
}