//http://www.infoarena.ro/problema/distante
#include <iostream>
#include <fstream>
#include <climits>
#include <set>
#include <vector>

using namespace std;

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

#define MAXN 50010

int n, S, d[MAXN];
vector <int> G[MAXN], C[MAXN], V;
set < pair <int, int> > T;


void Read()
{
    int m, x, y, c;
    f >> n >> m >> S;
    for(int i = 1; i <= n; i++)
        f >> x, V.push_back(x);
    for(int i = 1; i <= m; i++)
        f >> x >> y >> c, G[x].push_back(y), C[x].push_back(c);
}

void Dijkstra()
{
    int val, x;
    for(int i = 2; i <= n; i++)
        d[i] = INT_MAX;
    T.insert(make_pair(0, 1));
    while(T.size() > 0)
    {
        val = (*T.begin()).first; x = (*T.begin()).second;
        T.erase(*T.begin());
        for(int i = 0; i < G[x].size(); i++)
            if(d[ G[x][i] ] > val + C[x][i])
                d[ G[x][i] ] = val + C[x][i], T.insert(make_pair(d[ G[x][i] ], G[x][i]));
    }
}

int Verify()
{
    for(int i = 1; i <= n; i++)
        if(d[i] != V[i - 1])
            return 0;
    return 1;
}

int main()
{
    short gr;
    f >> gr;
    for(int i = 1; i <= gr; i++)
    {
        Read();
        Dijkstra();
        if(Verify()) g << "DA\n";
        else g << "NU\n";
        while(V.size()) V.pop_back();
        for(int i = 1; i <= n; i++){
            while(G[i].size()) G[i].pop_back();
            while(C[i].size()) C[i].pop_back();
        }
    }
}