#include <iostream>
#include <fstream>
#include <vector>
#include <queue>


using namespace std;

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

struct muchie
{
    int dir, cost;
};

struct zdrang
{
    int nod, dist;
};

#define MAX_N 50000
const int INF = 2e9;

vector<muchie> graf[MAX_N];
int d[MAX_N];
int dB[MAX_N];
bool vis[MAX_N];

priority_queue<int> pq;

int n, m;

void dijkstra()
{
    int node;
    while(!pq.empty())
    {
        node = pq.top();
        pq.pop();
        if(vis[node] == 0)
        {
            for(muchie i : graf[node])
            {
                int dir = i.dir, cost = i.cost;
                d[dir] = min(d[dir], d[node] + cost);
                pq.push(dir);
            }
            vis[node] = 1;
        }
    }
}

int main()
{
    int t, S, a, b, c;
    in >> t;
    for(int k = 0; k < t; ++k)
    {
        in >> n >> m >> S;
        for(int i = 0; i < n; ++i)
        {
            in >> dB[i];
            d[i] = INF;
            vis[i] = 0;
        }
        for(int i = 0; i < m; ++i)
        {
            in >> a >> b >> c;
            graf[a-1].push_back({b-1, c});
            graf[b-1].push_back({a-1, c});
        }

        d[S-1] = 0;
        pq.push(S-1);
        dijkstra();

        bool NU = 0;
        for(int i = 0; i < n; ++i)
        {
            cout << d[i] << " " << dB[i] << '\n';
            if(d[i] != dB[i])
            {
                out << "NU" << '\n';
                NU = 1;
                break;
            }
        }
        cout << "\n\n\n";
        if(NU == 0)
            out << "DA" << '\n';
    }

    return 0;
}