#include <bits/stdc++.h>

using namespace std;

ifstream f("distante.in");
ofstream g("distante.out");

int t, n, m, s;

int main()
{
    f >> t;

    for(int i = 0; i < t; i++)
    {
        bool ok = true;

        f >> n >> m >> s;

        int distante_b[n + 1], distante[n + 1];

        bool vizitat[n + 1];

        vector<pair<int, int>> lista[n + 1];

        for(int j = 1; j <= n; j++)
            lista[j].resize(n + 1);

        for(int j = 1; j <= n; j++)
        {
            f >> distante_b[j];

            vizitat[i] = false;
            distante[i] = INT_MAX;
        }

        for(int j = 1; j <= m; j++)
        {
            int x, y, z;

            f >> x >> y >> z;

            lista[x].push_back({y, z});
            lista[y].push_back({x, z});
        }

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

        distante[s] = 0;

        pq.push({0, s});

        while(!pq.empty())
        {
            int nod = pq.top().second;

            pq.pop();

            if(vizitat[nod])
                continue;

            vizitat[nod] = true;

            for(unsigned int j = 0; j < lista[nod].size(); j++)
            {
                int nod_2 = lista[nod][j].first;

                int cost = lista[nod][j].second;

                if(distante[nod_2] > distante[nod] + cost)
                {
                    distante[nod_2] = distante[nod] + cost;
                    pq.push({distante[nod_2], nod_2});
                }
            }
        }

        for(int j = 1; j <= n && ok; j++)
            if(distante[j] != distante_b[j])
            {
                g << "NU\n";
                ok = false;
            }

        if(ok)
            g << "DA\n";
    }
    return 0;
}