#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define dim 50001
#define inf 0x3f3f3f3f
using namespace std;
 
struct  comp{
    bool operator() (const pii &a,const pii &b)
    {
        return a.y>b.y;
    }
};
 
 
priority_queue <pii,vector<pii>,comp > H;
vector <pii> v[dim];
 
int nr,m,n,s,dist[dim],db[dim]; 

ifstream f("distante.in");
ofstream g("distante.out");
 
 
 
void read(){
     
 
    for(int i=1;i<=n;i++){
        v[i].clear();
    }
 
    int a,b,c;
    f>>n>>m>>s;
    for(int i=1;i<=n;i++)
        f>>db[i];         
 
    for(int i=1;i<=m;i++){
        f>>a>>b>>c;
        v[a].pb(mp(b,c));
        v[b].pb(mp(a,c));
    }
}

 
void Dijkstra(){
     
    if(db[s]!=0){ g << "NU\n"; return;}
    nr=1; 	
    int u,d,newd;
    memset(dist,inf,sizeof(dist));
    dist[s]=0;
    H=priority_queue<pii,vector<pii>,comp>();	
    H.push(mp(s,0));
    while(!H.empty()){
        u=H.top().x;
        d=H.top().y;
        H.pop();
        for(int i=0;i<int(v[u].size());i++){
            newd=d+v[u][i].y;
            if(newd<dist[v[u][i].x]){
                dist[v[u][i].x]=newd;
		if(newd<db[v[u][i].x]){ g << "NU\n"; return; }
                else if(newd==db[v[u][i].x]){ nr++; H.push(mp(v[u][i].x,newd));}
            }
        }
    }

    if(nr==n) g << "DA\n";
    else g << nr-n;	
}
 
 
int main(){
     
    int t;
    f>>t;
    for(int i=1;i<=t;i++){
        read();
        Dijkstra(); 
    }   
}