#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
using namespace std;

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

const int NMAX = 50000;
int cost[NMAX];

struct PATH{
    int nod,cost;
};
struct compara{
    bool operator()(int x,int y){
        return cost[x]>cost[y];
    }
};

vector<PATH> v[NMAX];
int dismin[NMAX];
bool isInQueue[10001];

priority_queue<int, vector<int>, compara>q;

int t,n,m,s;

int readIn(){
    in >> n >> m >>s;
    for(int i =1;i <=n;i++)
        in >> dismin[i];
    for(int i =0; i <m;i++){
        int a,b,c;
        in >> a >>b >>c;
        v[a].push_back({b,c});
    }
    return s;
}

void Dijkstra(int start){
    for (int i = 1; i <=n;i++){
        cost[i]=-1;
    }
    cost[start ] = 0;
    q.push(start);
    isInQueue[start] = true;
    while(!q.empty()){
        int nod = q.top();
        q.pop();
        isInQueue[nod] = false;
        for( PATH neigh_path : v[nod]){
            int neigh = neigh_path.nod;
            int c = neigh_path.cost;
            int NewC = cost[nod]+c;
            if(cost[neigh]==-1 || NewC <cost[neigh]){
                cost[neigh]=NewC;
                if(!isInQueue[neigh]){
                    q.push(neigh);
                    isInQueue[neigh]=true;
                }
            }
        }
    }
}
void resetdata(){
    for (int i = 0; i <=n;i++){
        dismin[i]=0;
        cost[i]=0;
        isInQueue[i]=0;
        v[i].clear();
    }
}

int main(){
    in >>t;
    for(int i =0; i <t;i++){
        int start= readIn();
        Dijkstra(start);
        bool check = true;
        for(int i =1; i <=n;i++){
            if(cost[i]!=dismin[i]){
                check = false;
            }
        }
        if(check){
            out << "DA\n";
        }else out << "NU\n";
        resetdata();
    }
}