#include <iostream>
#include<vector>
#include<queue>
#include<string>
#include<fstream>
  
using namespace std;
  
ifstream f("distante.in");
ofstream g("distante.out");
int T;
class graf
{
    int n,m,*frecventa,*distanta,*should_be,ok,S;
    bool *marcheaza;
    queue<int> coada;
    string in, out;
    struct muchie
    {
        int nod,cost;
    };
    vector<muchie> *lg;   //load graf
      
public:
    graf()
    {
        f >> n >> m >> S;
 
        marcheaza = new bool[n+1];
        frecventa = new int[n+1];
		should_be = new int[n+1];
        lg = new vector<muchie>[n+1];
        distanta = new int[n+1];
         
        int a;
        muchie b;
		for(int i=1;i<=n;++i)
			f>>should_be[i];
         for(int i=1;i<=m;i++)
        {
            f>>a>>b.nod>>b.cost;
            lg[a].push_back(b);
        }
    }
    
	
	bool check()
	{
		for(int i=1;i<=n;++i)
			if(should_be[i] != distanta[i])
				return false;

		return true;
	}
    void bellmanford()
    {
        int x;
 
        coada.push(S);
        marcheaza[S]=1;
 
        for(int i=1;i<=n;i++)
        {
            distanta[i]=1<<30;
            frecventa[i]=0;
            marcheaza[i]=0;
        }
        distanta[S]=0;
 
        while(!coada.empty())
        {
            x = coada.front();
            for(int i=0;i<lg[x].size();i++)
            {
                int nod = lg[x][i].nod;
                int cost = lg[x][i].cost;
                  
                if(distanta[x] + cost < distanta[nod])
                {
                    distanta[nod] = distanta[x] + cost;
                    if(!marcheaza[nod])
                    {
                        if(frecventa[nod]>n) {
                            g << "Ciclu negativ!";
                            return;
                        }
                        else
                        {
                            coada.push(nod);
                            marcheaza[nod]=1;
                            frecventa[nod]++;
                        }
                    }
                }
            }
            coada.pop();
            marcheaza[x]=0;
   
        }
        
    }
      
};
int main()
{
	f>>T;
	graf *x;
	while(T--)
	{
		x = new graf();
		x->bellmanford();
		if(x->check())
			g<<"DA\n";
		else g<<"NU\n";
		delete x;
		x = 0;
	}
	f.close();
	g.close();
	return 0;
}