#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>


#define min(a, b) ((a) < (b) ? (a) : (b))
#define LVECTTIME 15
#define MAXLONG 2147483647

typedef struct {
	long nr_vecini;
	long * vecini;
	long * cost; 
	long cost_from_source;
	long parent;   
	bool visited;   
} Nod;

//-----date intrare
Nod *graf;
long n,m,s,nr_grafuri,*d;
FILE* f;
FILE* f1;
//-----date intrare

void init_date(){
   	
	long i,j,a,b,c;

	fscanf(f,"%li %li %li",&n,&m,&s);
	
	graf = (Nod*)malloc((n+1)*sizeof(Nod));
    d = (long*)malloc((n+1)*sizeof(long));
 	
    for ( i = 0; i <= n; i++ ) {
        graf[i].vecini =(long*)malloc((n+1)*sizeof(long));
        graf[i].cost = (long*)malloc((n+1)*sizeof(long));        
        graf[i].nr_vecini=0;
        graf[i].parent =-1;
        graf[i].cost_from_source= MAXLONG;
		graf[i].visited = false;
    }
    graf[s].cost_from_source=0;
        
	for (i=1;i<=n;i++)
	   fscanf(f,"%li",&d[i]);      
    for (i=0;i<m;i++) {
        fscanf( f,"%li %li %li",&a,&b,&c);  
        graf[a].nr_vecini++;
		graf[b].nr_vecini++;	
		graf[a].vecini[graf[a].nr_vecini]=b;
		graf[b].vecini[graf[b].nr_vecini]=a;
		graf[a].cost[graf[a].nr_vecini]=c;
		graf[b].cost[graf[b].nr_vecini]=c;
    }
	
}

long next_node(){
    
    long c_min=MAXLONG,indexmin=0,i;
    
    for (i=1;i<=n;i++)
        if (!graf[i].visited){
            if (graf[i].cost_from_source<c_min){
                indexmin=i;
                c_min=graf[i].cost_from_source;
            }
        }
    return indexmin;
}
    
void dijkstra(){
    
    long i,indexmin=s;
    
    while (indexmin!=0){        
        for (i=1;i<=graf[indexmin].nr_vecini;i++){
            if (graf[graf[indexmin].vecini[i]].cost_from_source>graf[indexmin].cost_from_source+graf[indexmin].cost[i]){
                graf[graf[indexmin].vecini[i]].cost_from_source=graf[indexmin].cost_from_source+graf[indexmin].cost[i];
                graf[graf[indexmin].vecini[i]].parent=indexmin;
            }
        }
        graf[indexmin].visited=true;
        indexmin=next_node();        
    }
}

bool corect(){
    
    int i;
    for (i=1;i<=n;i++)
        if (d[i]!=graf[i].cost_from_source)
            return false;
    return true;
}

void free_data(){

	free(graf);
	free(d);
}

int main(){    
    
    f = fopen("distante.in","rt");
    
    f1 = fopen("distante.out","wt");
    fscanf(f,"%li",&nr_grafuri);
    
    while (nr_grafuri>0){
        init_date();
        dijkstra();
        if (corect())
            fprintf(f1,"DA\n");
        else
            fprintf(f1,"NU\n");
        free_data();
        nr_grafuri--;       
    }
    fclose(f);
    fclose(f1);
    return 0;   
}