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

#define MAXINT 2000000

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

Nod *graf;
int n,m,s,nr_grafuri,*d;
FILE* f;
FILE* f1;

void aloca(int nr){
    
    int i;
    graf = (Nod*)malloc(nr*sizeof(Nod));
    d = (int*)malloc(nr*sizeof(int));
    for ( i = 0; i < nr; i++ ) {
        graf[i].vecini =(int*)malloc(nr*sizeof(int));
        graf[i].cost = (int*)malloc(nr*sizeof(int));
    }
}

void init_date(){
   	
	int i,a,b,c;

	fscanf(f,"%i %i %i",&n,&m,&s);
    //graf = (Nod*)malloc(nr*sizeof(Nod));
    //d = (int*)malloc((nr*sizeof(int));	
 	
    for ( i = 0; i <= n; i++ ) {
        //graf[i].vecini =(int*)malloc((n+1)*sizeof(int));
        //graf[i].cost = (int*)malloc((n+1)*sizeof(int));        
        graf[i].nr_vecini=0;
        graf[i].parent =-1;
        graf[i].cost_from_source= MAXINT;
		graf[i].visited = false;
    }
    graf[s].cost_from_source=0;
        
	for (i=1;i<=n;i++)
	   fscanf(f,"%i",&d[i]);      
    for (i=0;i<m;i++) {
        fscanf( f,"%i %i %i",&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;
    }
	
}

int next_node(){
    
    int c_min=MAXINT,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(){
    
    int 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(){
    
    int i;
    for (i=0;i<=n;i++){
        free(graf[i].vecini);
        free(graf[i].cost);
    }
	free(graf);
	free(d);
}
*/
int main(){    
    
    f = fopen("distante.in","rt");    
    f1 = fopen("distante.out","wt");
    fscanf(f,"%i",&nr_grafuri);
    
    aloca(7500);
    //Am incercat sa fac alocare si free_data pentru fiecare graf dar imi dadea memory limit exceeded
    
    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;   
}