#include<stdio.h>
using namespace std;
const int N = 50005, M = 2 * 100005, INF = 500000000;
int verif[N], urm[M], vf[M], c[M], h[N], v[N], poz[N], nrh, nr, lst[N];
void adauga (int x, int y, int cost)
{
    vf[++nr] = y;
    c[nr] = cost;
    urm[nr] = lst[x];
    lst[x] = nr;
}
void schimba (int p1, int p2)
{
    int aux;
    aux = h[p1];
    h[p1] = h[p2];
    h[p2] = aux;
    poz[h[p1]] = p1;
    poz[h[p2]] = p2;
}
void urca (int p)
{
    while (p > 1 && v[h[p]] < v[h[p / 2]])
    {
        schimba (p, p / 2);
        p /= 2;
    }
}
void coboara (int p)
{
    int fs = p * 2, fd = p * 2 + 1, bun = p;
    if (fs <= nrh && v[h[fs]] < v[h[bun]])
        bun = fs;
    if (fd <= nrh && v[h[fd]] < v[h[bun]])
        bun = fd;
    if (bun != p)
    {
        schimba (bun, p);
        coboara (bun);
    }
}
void init (int n)
{
    int i;
    nrh = n;
    for (i = 1; i <= n; i++)
    {
        h[i] = i;
        v[i] = INF;
        poz[i] = i;
    }
}
void curatare (int n, int m)
{
    int i;
    nr = 0;
    for (i = 1; i <= n; i++)
        lst[i] = 0;
    for (i = 1; i <= m; i++)
    {
        urm[i] = 0;
        vf[i] = 0;
    }
}
int main ()
{
    FILE *in, *out;
    in = fopen ("distante.in", "r");
    out = fopen ("distante.out", "w");
    int t, teste, n, m, nod, i, cost, x, y, p;
    fscanf (in, "%d", &teste);
    bool ok;
    for (t = 1; t <= teste; t++)
    {
        fscanf (in, "%d%d%d", &n, &m, &nod);
        for (i = 1; i <= n; i++)
            fscanf (in, "%d", &verif[i]);
        for (i = 1; i <= m; i++)
        {
            fscanf (in, "%d%d%d", &x, &y, &cost);
            adauga (x, y, cost);
            adauga (y, x, cost);
        }
        init (n);
        v[nod] = 0;
        urca (poz[nod]);
        while (nrh > 0)
        {
            x = h[1];
            p = lst[x];
            schimba (nrh--, 1);
            coboara (1);
            while (p != 0)
            {
                y = vf[p];
                cost = c[p];
                if (v[x] + cost < v[y])
                {
                    v[y] = v[x] + cost;
                    urca (poz[y]);
                }
                p = urm[p];
            }
        }
        ok = true;
        for (i = 1; i <= n; i++)
            if (v[i] != verif[i])
                ok = false;
        if (ok == false)
            fprintf (out, "NU\n");
        else
            fprintf (out, "DA\n");
        curatare(n, m);
    }
    return 0;
}