#include<fstream>
#include<iostream>
#define nr 10000
using namespace std;
int maxi=10000;
int a[nr][nr],mini,d[nr],c,v[nr];
int i,n,m,t[nr],poz,j,s[nr],te,p,x,y,r,ok;
int main()
{ifstream f("distante.in");
ofstream g("distante.out");
f>>te;
for(p=1;p<=te;p++)
{ok=1;
    f>>n>>m>>r;
    for(i=1;i<=n;i++)
    f>>v[i];
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        if(i==j) a[i][j]=0;
    else a[i][j]=maxi;
       for(i=1;i<=m;i++)
       {
           f>>x>>y>>c;
    a[x][y]=a[y][x]=c;}
    for(i=1;i<=n;i++)
    {for(j=1;j<=n;j++)
        cout<<a[i][j]<<" ";
        cout<<endl;}
        s[r]=1;
        for(i=1;i<=n;i++)
            {
            {d[i]=a[r][i];
            if(i!=x)
                if(d[i]<maxi) t[i]=r;}}
        for(i=1;i<n;i++)
        {mini=maxi;
        for(j=1;j<=n;j++)
            if(s[j]==0)
                if(d[j]<mini)
                {mini=d[j];
                poz=j;}
                s[poz]=r;

    for(j=1;j<=n;j++)
        if(s[j]==0)
            if(d[j]>d[poz]+a[poz][j])
            {d[j]=d[poz]+a[poz][j];
            t[j]=poz;}}
        for(i=1;i<=n;i++)
            if(i!=r)
            if (d[i]!=v[i]) ok=0;
if(ok) g<<"DA"<<'\n';
else g<<"NU"<<'\n';}}