#include <bits/stdc++.h>
#define INF INT_MAX
using namespace std;
ifstream fin("distante.in");
ofstream fout("distante.out");
const int nmax = 50005;
int extractMin(priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>& pq){
    int temp = pq.top().second;
    pq.pop();
    return temp;
}

int main()
{   int T;
    fin >> T;
    while(T--) {
        int N, M, S;
        fin >> N >> M >> S;
        int bronzarel[N + 1];
        int dmin[N + 1];
        vector<pair<int, int>> adj[N + 1];
        for(int i = 1; i <= N; ++i) {
            fin >> bronzarel[i];
        }
        for(int i = 1; i <= M; ++i) {
            int src, dst, cost;
            fin >> src >> dst >> cost;
            adj[src].push_back(make_pair(dst, cost));
            adj[dst].push_back(make_pair(src, cost));
        }

        bool extracted[N + 1] = {false};
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push(make_pair(0, S));
        for(int i = 1; i <= N; ++i) {
            dmin[i] = INT_MAX;
        }
        dmin[S] = 0;
        while(pq.empty() == false) {
            int crt = extractMin(pq);
            if(extracted[crt] == false) {
                extracted[crt] = true;
                for(auto i: adj[crt]) {
                    int ngb = i.first;
                    int cost = i.second;
                    if(cost + dmin[crt] < dmin[ngb]) {
                        dmin[ngb] = cost + dmin[crt];
                        pq.push(make_pair(dmin[ngb], ngb));
                    }
                }
            }
        }
        int ok = 0;
        for(int i = 1; i <= N; ++i) {
            cout << dmin[i] << ' ';
        }
        cout << '\n';
        for(int i = 1; i <= N && ok == 0; ++i) {
            if(dmin[i] != bronzarel[i]) {
                fout << "NU\n";
                ok = 1;
            }
        }
        if(ok == 0)
            fout << "DA\n";
    }
    return 0;
}