#include<iostream>
#include<fstream>
#include<vector>
#define INFINIT 9999
using namespace std;
struct muchii
{
    unsigned a,b,c;
}v[100000];
unsigned n,m,s,D[50000];
bool Dijkstra(vector<unsigned>A[50000])
{
    bool vizitat[50000];
    unsigned long d[50000];
    cout<<A[1][0];
    vizitat[s]=1;
    for (unsigned i=1;i<=n;i++)
        d[i]=A[s][i];
    for (unsigned j=1;j<=n-1;j++)
    {
        unsigned minim=INFINIT, poz;
        for (unsigned k=1;k<=n;k++)
            if (!vizitat[k] && d[k]<minim)
            {
                minim=d[k];
                poz=k;
            }
        vizitat[poz]=1;
        for (unsigned i=1;i<=n;i++)
            if (!vizitat[i] && d[i]>(d[poz]+A[poz][i])) d[i]=d[poz]+A[poz][i];
    }
    bool ok;
    for (unsigned i=1;i<=n;i++)
        if (d[i]!=D[i])
            if (d[i]!=INFINIT && D[i]!=0) return 0;
}
int main()
{
    unsigned t;
    ifstream f("distante.in");
    ofstream f1("distante.out");
    f>>t;
    for (unsigned i=1;i<=t;i++)
    {
        f>>n>>m>>s;
        vector<unsigned>A[n];
        for (unsigned k=1;k<=n;k++)
            A[k].assign(n+1,INFINIT);
        for (unsigned j=1;j<=n;j++)
            f>>D[j];
        for (unsigned j=1;j<=m;j++)
            {
                unsigned a,b,c;
                f>>a>>b>>c;
                A[a][b]=A[b][a]=c;
            }
        if (Dijkstra(A)) f1<<"DA";
        else f1<<"NU";
    }
    return 0;
}