#include <iostream>
#include <stdio.h>
#include <vector>
#include <set>
using namespace std;

int main() {
    FILE *fin, *fout;
    int n, m, i, j, c, t, ns , x, y, nod, d, nodcurent, distanta, steag;
    vector <pair<int, int> > v[50001];
    int distdat[100001], distgg[100001];
    set <pair<int, int> > s;

fin = fopen("distante.in", "r");
fout = fopen("distante.out", "w");

fscanf(fin,"%d", &t);

for(j=1;j<=t;j++){

fscanf(fin,"%d%d%d", &n, &m, &ns);
for(i=1;i<=n;i++){
    distgg[i]=2000000000;
    distdat[i]=2000000000;
}







fscanf(fin,"%d%d%d", &n, &m, &ns);
for(i=1;i<=n;i++){
    while(v[i].empty()==false)
        v[i].pop_back();
}
while(s.empty()==false){
    s.erase(*s.begin());
}
for(i=1;i<=n;i++){
    fscanf(fin,"%d", &distdat[i]);
    for(i=1;i<=m;i++){
            fscanf(fin,"%d%d%d", &x, &y, &c);
            v[x].push_back(make_pair(y, c));
            v[y].push_back(make_pair(x, c));
    }

}


s.insert(make_pair(0, ns));
while(s.empty()==false){
  nod=(*s.begin()).second;
  d=(*s.begin()).first;
  s.erase(*s.begin());
  if(v[nod].empty()==false){
    for(i=0;i<=v[nod].size()-1;i++){
        nodcurent=v[nod][i].first;
        distanta=v[nod][i].second;
        if(distgg[nodcurent]>d+distanta){
            if(distgg[nodcurent]!=2000000001)
                s.erase(s.find(make_pair(distgg[nodcurent], nodcurent)));
            distgg[nodcurent]=d+distanta;
            s.insert(make_pair(distgg[nodcurent], nodcurent));
        }
    }
  }
}
steag=0;
for(i=1;i<=n;i++){
    if(distdat[i]!=distgg[i])
        steag=1;
}
if(steag==0)
    fprintf(fout,"DA\n");
else
    fprintf(fout,"NU\n");


}
fclose(fin);
fclose(fout);
    return 0;
}