#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 50005;
const int INF = (1 << 30);

int T, N, M, S, a, b, c;
int Dist[NMAX], InitialDist[NMAX];

struct compara {
    bool operator() (int x, int y) {
        return Dist[x] > Dist[y];
    }
};

vector< pair< int, int > > G[NMAX];
bitset< NMAX > checked;
priority_queue< int, vector< int >, compara > Q;

void Dijkstra(int startNode)
{
    for(int i = 1; i <= N; ++i)
        Dist[i] = INF;

    Dist[startNode] = 0;

    Q.push(startNode);
    checked[startNode] = 1;

    while(!Q.empty()) {
        int currentNode = Q.top();
        Q.pop();

        for(size_t i = 0; i < G[currentNode].size(); ++i) {
            int vecin = G[currentNode][i].first;
            int cost = G[currentNode][i].second;

            if(Dist[currentNode] + cost < Dist[vecin]) {
                Dist[vecin] = Dist[currentNode] + cost;

                if(!checked[vecin]) {
                    Q.push(vecin);
                    checked[vecin] = 1;
                }
            }
        }
    }
}

bool isMatch()
{
    Dist[1] = 0;
    for(int i = 1; i <= N; i++)
        if(Dist[i] != InitialDist[i])
            return false;

    return true;
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);

    fin >> T;
    for(int k = 0; k < T; ++k) {
        fin >> N >> M >> S;

        for(int i = 1; i <= N; ++i)
            fin >> InitialDist[i];

        for(int i = 0; i < M; ++i) {
            fin >> a >> b >> c;

            G[a].push_back({b, c});
        }

        Dijkstra(S);

        for(int i = 1; i <= N; i++)
            fout << Dist[i] << " ";
        fout << "\n";

        (isMatch() == true) ? fout << "DA\n" : fout << "NU\n";
    }
}