#include<fstream>
#include<iostream>
#define nr 10000
using namespace std;
int maxi=10000;
int a[nr][nr],mini,c,v[nr];
int i,n,m,poz,j,te,p,x,y,r,ok,k;
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(k=1;k<=n;k++)
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    if(a[i][j]>a[i][k]+a[k][j])
a[i][j]=a[i][k]+a[k][j];
for(i=1;i<=n;i++)
{
    for(j=1;j<=n;j++)
        cout<<a[i][j]<<" ";
    cout<<endl;
}
for(i=1;i<=n;i++)
           if(a[r][i]!=v[i]) ok=0;
if(ok) g<<"DA"<<'\n';
else g<<"NU"<<'\n';}}