#include <fstream>
#include <vector>
#include <queue>
using namespace std;
string file = "distante";
ifstream cin (file + ".in");
ofstream cout (file + ".out");
struct muchie{
    int nod,cost;

    inline bool operator() (const muchie &y) const
    {
        return cost > y.cost;
    }
};
const int N = 50001, INF = 50000001;
vector <muchie> L[N];
vector <int> d(N);
int n,m,k,v[N], h[10 + N], poz[N],nh;

inline void schimb(int x, int y)
{
    swap(h[x],h[y]);
    swap(poz[h[x]],poz[h[y]]);
}

inline void urca(int p)
{
    while (p>1 && d[h[p/2]] > d[h[p]])
    {
        schimb(p/2,p);
        p/=2;
    }
}

inline void coboara(int p)
{

    while (true)
    {
        int bun = p, fs = p*2, fd=p*2+1;
        if (fs <= nh && d[h[bun]] > d[h[fs]])
        {
            bun = fs;
        }
        if (fd <= nh && d[h[bun]] > d[h[fd]])
        {
            bun = fd;
        }
        if (bun == p)
            break;
        schimb(bun,p);
        p = bun;
    }
}

inline void adauga(int nod)
{
    h[++nh] = nod;
    poz[nod] = nh;
    urca(nh);
}
inline void sterge(int p)
{
    schimb(p,nh);
    nh--;
    urca(p);
    coboara(p);
}
void bfs (int x)
{
    d[x] = 0;
    h[++nh] = x;
    while (nh)
    {
        x = h[1];
        sterge(1);
        for (auto y : L[x])
        {
            if (d[y.nod] > d[x] + y.cost)
            {
                d[y.nod] = d[x] + y.cost;
                if (poz[y.nod] == 0)
                {
                    adauga(y.nod);
                }
                else
                {
                    urca(poz[y.nod]);
                }
            }
        }
    }
}
int main()
{
    int t,a,b,c;
    cin >> t;
    while (t--)
    {
        cin >> n >> m >> k;
        for (int i=1; i<=n; i++)
        {
            L[i].clear();
            d[i] = INF;
            cin >> v[i];
        }

        while (m--)
        {
            cin >> a >> b >> c;
            L[a].push_back({b,c});
            L[b].push_back({a,c});
        }
        bfs(k);

        bool ok = 1;
        for (int i=1; i<=n; i++)
        {
            if (v[i] != d[i])
            {
                ok = 0;
                break;
            }
        }
        cout << (ok == 1 ? "DA\n" : "NU\n");
    }
}