#include <iostream>
#include <fstream>
#include <vector>
#define MAX 50005
#define INF 9999999

using namespace std;

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

struct nod
{
    int y, c;
};

struct heap
{
    int val, poz;
} H[MAX];

vector <nod> G[MAX];
int dis[MAX], n, m, start, lung, v[MAX];
bool viz[MAX];

void citire()
{
    int j;
    for( j = 0; j <= n; ++j)
        G[j].clear();

    int x, y, cost;
    f >> n >> m >> start;
    for (int i = 1; i <= n; i++)
        f >> v[i];

    for (int i = 1; i <= m; i++)
    {
        f >> x >> y >> cost;
        G[x].push_back({y, cost});
        G[y].push_back({x, cost});
    }

    for (int i = 1; i <= n; i++)
    {
        dis[i] = INF;
        viz[i] = 0;
    }
    dis[start] = 0;
    f.close();
}

void insert_heap(int &lung, int x, int poz)
{
    int tata, fiu;
    lung++;
    fiu = lung;
    tata = lung / 2;
    H[fiu].val = x;
    H[fiu].poz = poz;

    while (tata > 0 && H[tata].val > H[fiu].val)
    {
        swap(H[tata], H[fiu]);
        fiu = tata;
        tata = fiu / 2;
    }
}

int extract_heap(int &lung)
{
    int tata = 1, fiu = 2, x;
    x = H[1].poz;
    H[1].poz = H[lung].poz;
    H[1].val = H[lung].val;
    --lung;
    while (fiu <= lung)
    {
        if (fiu + 1 <= lung)
            if (H[fiu].val > H[fiu + 1].val)
                ++fiu;
        if (H[tata].val > H[fiu].val)
        {
            swap(H[tata], H[fiu]);
            tata = fiu;
            fiu = fiu * 2;
        }
        else
            break;
    }
    return x;
}
void dijkstra(int start)
{
    int i, vecin, cost, minn;
    insert_heap(lung, dis[start], start);
    viz[start] = 1;

    while (lung)
    {
        minn = extract_heap(lung);
        viz[minn] = 0;
        for (i = 0; i < G[minn].size(); i++)
        {
            vecin = G[minn][i].y;
            cost = G[minn][i].c;
            if (dis[vecin] > dis[minn] + cost)
            {
                dis[vecin] = dis[minn] + cost;
                if (viz[vecin] == 0)
                {
                    insert_heap(lung, dis[vecin], vecin);
                    viz[vecin] = 1;
                }
            }
        }
    }
}

void afisare()
{
    int j;
    for(j = 1; j <= n; j++)
        if(dis[j] != v[j])
            break;
    if(j > n)
        g<<"DA"<<'\n';
    else
        g<<"NU"<<'\n';
}

int main()
{
    int teste;
    f >> teste;
    for (int i = 1; i <= teste; i++)
    {
        citire();
        dijkstra(start);
        afisare();
    }
    return 0;
}