#include <bits/stdc++.h>
#include <limits>

using namespace std;

int infinit = std::numeric_limits<int>::max();

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



class Graf
{
    int nr_N, nr_M, S;

public:

    /// Constructori
    Graf() : nr_N(0), nr_M(0) {}
    Graf(int N, int M) : nr_N(N), nr_M(M) {}

    void Dijkstra(int&, int&, int&, vector<int>&, vector<int>&, vector<vector<pair<int,int>>>&);
};

void Graf::Dijkstra(int& nr_N, int& nr_M, int& S, vector<int>& comp, vector<int>& dist,vector<vector<pair<int,int>>>& costuri)
{
    int V[100001] = {};

    for(int i = 1; i <= nr_N; i++)
        dist[i] = infinit;

    dist[S]=0;

    priority_queue<pair<int,int>> H; /// Va sorta singur in functie de cea mai mica distanta
    H.push({0,1});

    while(H.size() > 0)
    {
        int u = H.top().second;
        H.pop();
        if(V[u])
            continue;
        else
            V[u]++;
        for(auto v : costuri[u]) /// Verificam toti vecinii lui u
        {
            if(dist[v.first] > dist[u] + v.second)
            {
                dist[v.first] = dist[u] + v.second;
                H.push({-dist[v.first], v.first}); /// Folosim -dist[v.first] ca sa avem in top cea mai mica valoare
            }
        }
    }
}


int t, nr_N, nr_M, S;

int main()
{

    in >> t;
    for(int i = 1; i <= t; i++)
    {

        Graf G;
        in >> nr_N >> nr_M >> S;
        vector<int> comp(nr_N + 1, 0), dist(nr_N + 1, 0);

        for(int i = 1; i <= nr_N; i++)
        {
            int x;
            in >> x;
            comp[i] = x;
        }

        vector<vector<pair<int,int>>> costuri(nr_N + 1);
        for(int i = 1; i <= nr_M; i++)
        {
            int x, y, c;
            in >> x >> y >> c;
            costuri[x].push_back({y,c}); /// Muchia de la x plecand in y are costul c
            costuri[y].push_back({x,c});
        }

        G.Dijkstra(nr_N, nr_M, S, comp, dist, costuri);

        int ok = 1;
        for(int i = 1; i <= nr_N; i++)
        {
            cout << dist[i] << " " << comp[i] << endl;
            if(dist[i] != comp[i])
                ok = 0;
        }
        if(ok)
            out << "DA" << '\n';
        else
            out << "NU" << '\n';

    }
    return 0;
}