#include <fstream>
using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");
#define inf (1<<16)
int c[10001][10001],d[10001],di[10001],t[10001],s[10001],n,m,xp,w;
void cit(){
    int i,j,x,y,z;
    f>>n>>m>>xp;
    for(i=1;i<=n;i++)
        f>>di[i];
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++)
            c[i][j]=inf;
        c[i][i]=0;}
    for(i=1;i<=m;i++){
        f>>x>>y>>z;
        c[x][y]=z;}
}
int min(int &q){
    int i,Min=inf+1;
    for(i=1;i<=n;i++)
        if(!s[i] && Min>d[i]){
            Min=d[i];
            q=i;}
    }
void det_drumuri(){
    int i,j,ok,x,k;
    for(i=1;i<=n;i++){
        d[i]=c[xp][i];
        s[i]=0;
        if(c[xp][i]<inf)
            t[i]=xp;
        else t[i]=0;}
    t[xp]=0;s[xp]=1;ok=1;x=0;
    do{ min(k);
        x++;
        if(d[k]==inf || x==n)
            ok=0;
        else{
            s[k]=1;
            for(j=1;j<=n;j++)
                if(!s[j] && d[j]>d[k]+c[k][j]){
                    d[j]=d[k]+c[k][j];
                    t[j]=k;}
        }
    } while(ok);
}
int main()
{
    f>>w;
    for(int i=1;i<=w;++i){
        int sw=1;
        cit();
        det_drumuri();
        for(int j=1;j<=n;j++)
            if(di[j]!=d[j])
                sw=0;
        if(sw)
            g<<"DA";
        else
            g<<"NU";
        g<<'\n';}
    return 0;
}