#include <bits/stdc++.h>
#define NMAX 50005
#define INF 0xf3f3f3
using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");
int costInput[NMAX];
int cost[NMAX];
int n,m,sursa,nrGf;
void check(){
    for(int i=1;i<=n;i++){
        if(cost[i]==INF)cost[i]=0;
        if(costInput[i]!=cost[i]){
            g<<"NU\n";
            return;
        }
    }
    g<<"DA\n";
}
void rez(){
    cost[sursa]=0;
    for(int i=1;i<=m;i++){
        int a,b,c;
        f>>a>>b>>c;
        cost[a]=min(cost[a],costInput[b]+c);
        cost[b]=min(cost[b],costInput[a]+c);
    }
}
int main()
{
    f>>nrGf;
    for(int k=1;k<=nrGf;k++){
        f>>n>>m>>sursa;
        for(int i=1;i<=n;i++){
            cost[i]=INF;
            f>>costInput[i];
        }
        rez();
        check();
    }
    return 0;
}