#include <fstream>
#include <vector>
#define INF 0x3f3f3f3f
#define nodv g[nod][i].second
#define valv g[nod][i].first
using namespace std;

ifstream is("distante.in");
ofstream os("distante.out");

class Heap{
public:
    Heap(int siz) : nH(0), P(siz)
    {
        H.push_back(0);
        C.push_back(0);
    }
    int size()
    {
        return nH;
    }
    int top()
    {
        return H[1];
    }
    bool inH(int nod)
    {
        if ( P[nod] )
            return true;
        return false;
    }
    void Change(int val, int nod)
    {
        C[P[nod]] = val;
        up(nod);
    }
    void push(int val, int nod)
    {
        H.push_back(nod);
        C.push_back(val);
        P[nod] = ++nH;
        up(nH);
    }
    void up(int down)
    {
        int up = down / 2;
        while ( up && C[up] > C[down] )
        {
            Swap(up, down);
            down /= 2;
            up /= 2;
        }
    }
    void pop()
    {
        P[H[1]] = 0;
        H[1] = H[nH];
        C[1] = C[nH];
        P[H[nH--]] = 1;
        int up = 1, down = 2;
        while ( ( down <= nH && C[up] > C[down] ) || ( down < nH && C[up] > C[down + 1] ) )
        {
            if ( down < nH && C[down + 1] < C[down] )
                ++down;
            Swap(up, down);
            up = down;
            down *= 2;
        }
    }
    void Swap(int n1, int n2)
    {
        swap(P[H[n1]], P[H[n2]]);
        swap(H[n1], H[n2]);
        swap(C[n1], C[n2]);
    }
private:
    int nH;
    vector<int> H, C, P;
};

int t, n, m, s;

void Solve();

int main()
{
    is >> t;
    while ( t-- )
        Solve();
    is.close();
    os.close();
    return 0;
}

void Solve()
{
    is >> n >> m >> s;
    vector<vector<pair<int, int> > > g(n + 1);
    vector<int> d(n + 1, INF), D(n + 1);
    d[s] = 0;
    for ( int i = 1; i <= n; ++i )
        is >> D[i];
    int n1, n2, c;
    while ( m-- )
    {
        is >> n1 >> n2 >> c;
        g[n1].push_back(make_pair(c, n2));
        g[n2].push_back(make_pair(c, n1));
    }
    Heap hp(n + 1);
    hp.push(0, 1);
    int nod;
    while ( hp.size() )
    {
        nod = hp.top();
        hp.pop();
        for ( size_t i = 0; i < g[nod].size(); ++i )
            if ( d[nodv] > d[nod] + valv )
            {
                d[nodv] = d[nod] + valv;
                if ( hp.inH(nodv) )
                    hp.Change(d[nodv], nodv);
                else
                    hp.push(d[nodv], nodv);
            }
    }
    for ( int i = 1; i <= n; ++i )
        if ( D[i] != d[i] )
        {
            os << "NU\n";
            return;
        }
    os << "DA\n";
}