#include <bits/stdc++.h>
using namespace std;

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

int t;
int n,m,r;
int x,y,c;
vector < pair < int , int > > v[50005];
int distemp[50005],distreal[50005];
int oo = 2000000007;
set < pair < int , int > > st;
bool ok;

void initialize() {
    for (int i=1;i<=n;i++) {
        distreal[i] = oo;
        v[i].clear();
    }
}

void read_graph() {
    for (int i=1;i<=m;i++) {
        f >> x >> y >> c;
        v[x].push_back({y,c});
    }
}

void dijkstra() {
    distreal[r] = 0;
    st.insert({0,r});
    while (st.empty()==0) {
        int nod = st.begin()->second;
        st.erase(st.begin());
        for (auto k:v[nod]) {
            if (distreal[k.first] > distreal[nod] + k.second) {
                st.erase({distreal[k.first],k.first});
                distreal[k.first] = distreal[nod] + k.second;
                st.insert({distreal[k.first],k.first});
            }
        }
    }
}

bool verify() {
    for (int i=1;i<=n;i++) {
        if ((distreal[i]!=distemp[i] && distreal[i]!=oo) || (distreal[i]==oo && distemp[i]!=0)) {
            return 0;
        }
    }
    return 1;
}

int main()
{
    f >> t;
    for (int u=1;u<=t;u++) {
        f >> n >> m >> r;
        initialize();
        read_graph();
        dijkstra();
        ok = verify();
        if (ok==1) {
            g << "DA" << '\n';
        }
        else {
            g << "NU" << '\n';
        }
    }
    return 0;
}