#include<iostream>
#include<fstream>
#include<vector>
#include<set>
#include<utility>
using namespace std;
ifstream fin("distante.in");
ofstream fout("distante.out");
int t,n,m,s;

void solve()
{   int x,y,c,nod;
   vector<int>d(n+1);
   for(int i=1;i<=n;i++)
        fin>>d[i];
   vector<pair<int,int> > g[n+1];
   for(int i=1;i<=m;i++)
 {
     fin>>x>>y>>c;
     g[x].push_back(make_pair(y,c));
     g[y].push_back(make_pair(x,c));
 }
  vector<int>dmin(n+1,10000000);
  dmin[1]=0;
  set<pair<int,int> >st;
  st.insert(make_pair(0,1));
     while(!st.empty())
     {
         nod=st.begin()->second;
         st.erase(st.begin());
         for(int i=0;i<g[nod].size();++i)
         {
             if(dmin[g[nod][i].first]>dmin[nod]+g[nod][i].second)
             {
                 dmin[g[nod][i].first]=dmin[nod]+g[nod][i].second;
                 st.insert(make_pair(dmin[g[nod][i].first],g[nod][i].first));
             }
         }
    }
    int verif=1;
    for(int i=1;i<=n&&verif;i++)
          if(d[i]!=dmin[i])verif=0;
if(verif)fout<<"DA"<<'\n';
else fout<<"NU"<<'\n';

}
int main()
{
    fin>>t;
    for(int i=1;i<=t;i++)
    {
        fin>>n>>m>>s;
        solve();
    }
    fin.close();
    fout.close();
    return 0;
}