#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
using namespace std;

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

const int dmax = 50000;
const int dim = 100000;
const int INF = 100000005;

struct MUCHIE
{
    int a, b, cost;
};
MUCHIE m[2*dim + 1];

int k;

int inc[dmax + 1];

int v[dmax + 1];

int d[dmax + 1];
bool viz[dmax + 1];

int N, M, S, T;

bool exc(MUCHIE e1, MUCHIE e2)
{
    if(e1.a == e2.a) return e1.b < e2.b;
    else
        return e1.a < e2.a;
}

void Initializare()
{
    int i, x, y, cost;

    in >> N >> M >> S;

    for(i = 1; i <= N; i++) in >> v[i];

    for(i = 1; i <= M; i++)
    {
        in >> x >> y >> cost;

        k++;
        m[k].a = x;
        m[k].b = y;
        m[k].cost = cost;

        k++;
        m[k].a = y;
        m[k].b = x;
        m[k].cost = cost;
    }

    sort(m + 1, m + k + 1, exc);

    inc[ m[1].a ] = 1;

    for(i = 2; i <= k; i++)
        if(m[i].a != m[i-1].a) inc[ m[i].a ] = i;

    for(i = 1; i <= N; i++) d[i] = INF;

    viz[S] = true;
    d[S] = 0;

    //PARCURG LISTA VECINILOR NODULUI S
    for(i = inc[S]; m[i].a == S; i++)
        //m[i].b
        d[ m[i].b ] = m[i].cost;
}

void Dijkstra()
{
    int i, j, d_min, nod;

    for(j = 1; j < N; j++)
    {
        d_min = INF;

        for(i = 1; i <= N; i++)
            if(!viz[i] && d_min > d[i])
            {
                d_min = d[i];
                nod = i;
            }

        viz[nod] = true;

        //PARCURG VECINII NODULUI nod

        for(i = inc[nod]; m[i].a == nod; i++)
            //m[i].b
            if( d[ m[i].b ] > d[ nod ] + m[i].cost ) d[ m[i].b ] = d[ nod ] + m[i].cost;
    }
}

void Afisare()
{
    for(int i = 1; i <= N; i++) printf("%d ", d[i]);
    printf("\n");
}

void Verificare()
{
    bool answer = true;

    for(int i = 1; i <= N; i++)
        if(d[i] != v[i]) answer = false;

    if(answer == true) out << "DA" << '\n';
    else
        out << "NU" << '\n';
}

int main()
{
    in >> T;

    for(int i = 1; i <= T; i++)
    {
        k = 0;
        memset(v, 0, sizeof(v));
        memset(inc, 0, sizeof(inc));
        memset(d, 0, sizeof(d));
        memset(viz, false, sizeof(viz));
        memset(m, 0, sizeof(m) );

        Initializare();
        Dijkstra();
        //Afisare();
        Verificare();
    }

    return 0;
}