#include <bits/stdc++.h>
#define inf 2000000000
using namespace std;

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

struct date{
    int nod,cost;
};

vector<date>v[50005];
int dis[50005];
int dp[50005];
bool vis[50005];
queue<int>q;
int i,a,b,s,m,n,c,t;

void reseteaza(){
    for(int i=1;i<=n;i++){

        while(!v[i].empty()){
            v[i].pop_back();
        }
        dp[i]=inf;
        dis[i]=0;
    }
    while(!q.empty()){
        q.pop();
    }
}

void Djakstra(){
    int w;
    w=1;
    q.push(w);
    dp[1]=0;
    while(!q.empty()){
        w=q.front();
        q.pop();

        for(auto i:v[w]){
            if(dp[i.nod]>dp[w]+i.cost){

                dp[i.nod]=dp[w]+i.cost;
                q.push(i.nod);
            }
        }
    }

}

void rez(){
    Djakstra();
    int veri=1;
    for(int i=1;i<=n;i++){
       // cout<<dp[i]<<" ";
        if(dp[i]!=dis[i]){
            veri=0;
        }
    }
    if(veri==1){
        cou<<"DA \n";
    }else{
        cou<<"NU \n";
    }
}

void citire(){
    ci>>t;
    while(t--){

        ci>>n>>m>>s;
        reseteaza();
        for(int i=1;i<=n;i++){
            ci>>dis[i];
        }
        date p;
        for(int i=1;i<=m;i++){
            ci>>a>>b>>c;
            p.cost=c;
            p.nod=b;
            v[a].push_back(p);
            p.nod=a;
            v[b].push_back(p);
        }

        rez();

    }
}

int main()
{
    citire();
    return 0;
}