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

#define maxx 50002
#define cost first
#define nod second
#define inf 0x3f3f3f3f

using namespace std;

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

int n,m,j,c,i,viz[maxx],rez[maxx],T,s,corect,x;
vector < pair <int,int> > G[maxx];
vector < pair <int,int> > :: iterator it;
priority_queue < pair < int, int >, vector < pair < int, int > >, greater < pair < int, int > > > pq;
pair <int, int> aux;

void dijkstra ( int inc )
{
    pq.push( { 0 , inc } );
    while( !pq.empty( ) )
    {
        aux = pq.top( );
        pq.pop( );
        if(viz[ aux.nod ] )
            continue;
        viz[ aux.nod ] = aux.cost;
        int nn = G[ aux.nod ].size();
        for( int r = 0;r < nn ; r++ )
        {
            if(viz[G[aux.nod][r].nod]==0&&G[aux.nod][r].nod!=s)
                pq.push({aux.cost+G[aux.nod][r].cost,G[aux.nod][r].nod});
        }

    }
}

int main()
{
    f>>T;
    for(int k=0;k<T;k++)
    {
        f>>n>>m>>s;

        for(i=1;i<=n;i++)
        {
            f>>rez[i];
        }
        for(int r=1;r<=m;r++)
        {
            f>>i>>j>>c;
            G[i].push_back(make_pair(c,j));
            G[j].push_back(make_pair(c,i));
        }
        dijkstra(s);

        corect=1;
        for(i=1;i<=n;i++)
        {
            if(i==s)
            {
                viz[i]=0;
            }
            if(viz[i]!=rez[i])
                corect=0;
            cout<<viz[i]<<" "<<rez[i]<<'\n';
        }
        cout<<'\n';
        if(corect==1)
            g<<"DA"<<'\n';
        else
            g<<"NU"<<'\n';
        memset( viz, 0 , sizeof( viz ) );
        for( int r = 1; r <= n; r++ )
        {
            G[ r ].clear( );
        }

    }
    f.close();
    g.close();
    return 0;
}