#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

const int MAXN = 50005,INF = 2e9;

using namespace std;

typedef pair<int,int> pii;

ifstream in("distante.in");
ofstream out("distante.out");

vector<pii>graf[MAXN];
priority_queue<pii, vector<pii>, greater<pii> >heap;
int n,m,start,dp[MAXN],calc[MAXN];
bool viz[MAXN];

void initialize(){
    for(int i = 0; i <= n; i++){
        graf[i].clear();
        viz[i] = false;
    }
    while(!heap.empty())
        heap.pop();
}
void dijsktra(int start){
    for(int i = 1; i <= n; i++)
        dp[i] = INF;
    heap.push({0,start});
    dp[start] = 0;

    while(heap.size()){
        int nod = heap.top().second;
        heap.pop();
        if(!viz[nod]){
            for(int i = 0; i < graf[nod].size(); i++){
                pii curent = graf[nod][i];
                int vecin = curent.first,cost = curent.second;
                if(dp[nod] + cost < dp[vecin]){
                    dp[vecin] = dp[nod] + cost;
                    heap.push({dp[vecin],vecin});
                }
            }
        }
    }
}
string solve(){
    in>>n>>m>>start;
    initialize();
    for(int i = 1; i <= n; i++)
        in>>calc[i];
    for(int i = 1; i <= m; i ++){
        int nod,muchie,cost;
        in>>nod>>muchie>>cost;
        graf[nod].push_back({muchie,cost});
        graf[muchie].push_back({nod,cost});
    }

    dijsktra(start);
    for(int i = 1; i <= n; i++)
        if(dp[i] != calc[i])
            return "NU";
    return "DA";
}
int main()
{
    in.tie(NULL);
    out.tie(NULL);
    ios::sync_with_stdio(false);

    int t;
    in>>t;
    for(int i = 1; i <= t; i++)
        out<<solve()<<"\n";
    return 0;
}