#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;
        heap.insert(make_pair(0, k));
        while(!heap.empty())
        {
            nod=heap.begin()->second;
            cost=heap.begin()->first;
            viz[nod]=1;
            if(vd[nod]!=d[nod])
                break;
            heap.erase(heap.begin());
            for(vector< pair<int, int> > :: iterator it=l[nod].begin(); it!=l[nod].end(); it++)
            {
                vecin=it->first;
                costv=it->second;
                if(d[vecin]>costv+cost && viz[vecin]==0)
                {
                    heap.erase(make_pair(d[vecin], vecin));
                    d[vecin]=costv+cost;
                    heap.insert(make_pair(d[vecin], vecin));
                }
            }
        }
        if(!heap.empty())
        {
            g<<"NU\n";
        }
        else g<<"DA\n";
        t--;
    }
    return 0;
}