#include<iostream>
#include <fstream>
#include<vector>
#include<queue>
#include<cstdio>
#include<algorithm>
#define lim 60000
#define inf 1<<30
using namespace std;
class distante {
    int t,n,m,s;
    int dist[lim];
    bool incoada[lim];
    struct muchie
    {
        int nod;
        int cost;
    };
    vector<muchie> G[lim];
    queue<int> coada;
    fstream in,out;
public:
    distante(string fin,string fout)
    {
        in.open(fin.c_str(), ios::in);
        out.open(fout.c_str(), ios::out);
    }
    ~distante()
    {
        in.close();
        out.close();
    }
    void bford()
    {
        int cost,x,y;
        coada.push(s);
        for(int i=1;i<=n;i++)
        {
            dist[i]=inf;
            incoada[i]=false;
        }
        dist[s]=0;
        incoada[s]=true;
        while(!coada.empty())
        {
            x=coada.front();
            //cout<<endl<<x<<endl;
            coada.pop();
            for(int i=0;i<G[x].size();i++)
            {
                y=G[x][i].nod;
                cost=G[x][i].cost;
                cout<<dist[x]+G[x][i].cost<<" "<<dist[G[x][i].nod]<<endl;
                if(dist[x]+G[x][i].cost<dist[G[x][i].nod])
                {
                    if(incoada[y]==false)
                    {
                        cout<<"in coada: "<<y<<endl;
                        coada.push(y);
                        incoada[y]=true;
                    }
                    dist[y]=dist[x]+cost;
                }
            }
        }


    }
    void solve()
    {
        in>>t;
        muchie a,b;
        bool ok;
        int d[lim];
        while(t--)
        {
            in>>n>>m>>s;
            //cout<<n<<" "<<m<<" "<<s<<endl;
            for(int i=1;i<=n;i++)
            {
                in>>d[i];
            }

            for(int i=1;i<=m;i++)
            {
                in>>a.nod>>b.nod>>b.cost;
                G[a.nod].push_back(b);
                a.cost=b.cost;
                G[b.nod].push_back(a);
            }
            if(d[s]==0)
            {
                bford();
                for(int j=1;j<=n;j++)
                    cout<<dist[j]<<" "<<d[j]<<endl;
                cout<<endl;
                ok=true;
                for(int i=1;i<=n;i++)
                {
                    if(d[i]!=dist[i])
                    {
                        out<<"NU"<<endl;
                        i=n;
                        ok=false;
                    }
                }
                if(ok==true)
                {
                    out<<"DA"<<endl;
                }
            }
            else
            {
                out<<"NU"<<endl;
            }
            for(int i=1;i<=n;i++)
            {
                for(int j=0;j<G[i].size();j++)
                {
                    G[i].clear();
                }
            }
        }
    }
};
int main()
{
    distante X("distante.in","distante.out");
    X.solve();
    return 0;
}