#include <fstream>
#include <vector>
#include <set>
#define inf 214700000
using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");
int n, m, i, k, sol[50002], x, y, t, c, cost, vd[50002], d[50002], nod, vecin, costv;
bool viz[50002];
int main()
{
    f>>t;
    while(t!=0)
    {
        vector<pair<int, int> > l[100002];
        set<pair<int, int> > heap;
        f>>n>>m>>k;
        for(i=1;i<=n;i++)
        {
            f>>vd[i];
            viz[i]=0;
            d[i]=inf;
        }
        for(i=1;i<=m;i++)
        {
            int x, y, c;
            f>>x>>y>>c;
            l[x].push_back(make_pair(y, c));
            l[y].push_back(make_pair(x, c));
        }
        d[k]=0;
        bool ok=0;
        heap.insert(make_pair(0, k));
        while(!heap.empty() && ok==0)
        {
            nod=heap.begin()->second;
            viz[nod]=1;
            if(vd[nod]==d[nod])
            {
                heap.erase(heap.begin());
                for(vector< pair<int, int> > :: iterator it=l[nod].begin(); it!=l[nod].end(); it++)
                {
                    vecin=it->first;
                    cost=it->second;
                    if(d[vecin]>d[nod]+cost && viz[vecin]==0)
                    {
                        heap.erase(make_pair(d[vecin], vecin));
                        d[vecin]=d[nod]+cost;
                        heap.insert(make_pair(d[vecin], vecin));
                    }
                }
            }
            else ok=1;
        }
        if(ok)
            g<<"NU\n";
        else g<<"DA\n";
        t--;
    }
    return 0;
}