#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>
#include <string>
#include <typeinfo>
#include <bits/stdc++.h>
using namespace std;
#include <iostream>
using namespace std;

ifstream fin("date.in");
ofstream fout("date.out");
int N,M,sursa;
double dist[1000];
typedef struct
{
    inline bool operator ()(const int i ,const int j)
    {
        return (dist[i]>dist[j]);
    }
}compare;
priority_queue< int , vector<int>, compare > Q;
vector < pair<int,int> > v[1000];
vector <int> vectorul_initial;
vector <int> vectorul_final;

bool tata[1000];
    int inf=1e9,i;
void citire()
    {
        fin>>N>>M>>sursa;
        cout<<sursa<<"\n";
        for(i=0;i<N;i++)
        {
            int t;
            fin>>t;
            vectorul_initial.push_back(t);
        }
        for(i=1;i<=M;i++)
        {
            int a,b,c;
            fin>>a>>b>>c;
            v[a].push_back({b,c});
            v[b].push_back({a,c});
        }
    }
    void Dijkstra()
{
    for(i=1;i<=N;i++)
    {
        dist[i]=inf;
        tata[i]=0;
    }
    Q.push(sursa);
    tata[sursa]=1;
    dist[sursa]=0;
    while(!Q.empty())
    {
        int x,y;
        double cost;
        x=Q.top();
        tata[x]=0;
        Q.pop();
        for(i=0;i<v[x].size();i++)
        {
            y=v[x][i].first;
            cost=v[x][i].second;
            if(dist[x]+cost<dist[y])
            {
                dist[y]=dist[x]+cost;
                if(tata[y]==0)
                {
                    tata[y]=1;
                    Q.push(y);
                }
            }
        }
    }
    for(i=1;i<=N;i++)
    {
        if(dist[i]==inf || dist[i]==sursa)
     {
                dist[i]=0;
     }
     vectorul_final.push_back(dist[i]);
    }
    for(i=1;i<=N;i++)
    {
        fout<<dist[i]<<" ";
    }
    fout<<"\n";
}
void verificare()
{
    if(vectorul_final==vectorul_initial)
        fout<<"DA\n";
    else
        fout<<"NU\n";
}

int main()
{
    int T,i;
    fin>>T;
    for(i=1;i<=T;i++)
    {
        citire();
        Dijkstra();
        verificare();
    }
    fin.close();
    fout.close();
    return 0;
}