#include <fstream>
#include <vector>

using namespace std;

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

const int oo=2000000000;
const int Nmax=50000;

int NrNoduri, NrMuchii, nrGrafuri, nodSursaGlobal;
int distanta[Nmax], vizitat[Nmax];
int distantaPresupusa[Nmax];


vector < pair < int, int > > listaVecini[Nmax];

void Read()
{
    fin >> NrNoduri >> NrMuchii >> nodSursaGlobal;
    for (int i=1; i<=NrNoduri; i++)
        fin >> distantaPresupusa[i];
    for (int i=1; i<=NrMuchii; i++)
    {
        int nod, vecin, cost;
        fin >> nod >> vecin >> cost;
        listaVecini[nod].push_back(make_pair(vecin, cost));
    }
}

void Dijkstra(int nodSursaArgument)
{
    int nodCurent, distMinima;

    distanta[nodSursaArgument]=0;
    for (int i=1; i<=NrNoduri; i++)
        if (i!=nodSursaArgument)
            distanta[i]=oo;

    for (int k=1; k<NrNoduri; k++)
    {
        distMinima=oo;
        for (int i=1; i<=NrNoduri; i++)
            if (distanta[i]<distMinima && vizitat[i]==0)
                distMinima=distanta[i], nodCurent=i;

        vizitat[nodCurent]=1;

        for (int i=0; i<(int)listaVecini[nodCurent].size(); i++)
        {
            int nodVecin=listaVecini[nodCurent][i].first;
            int cost=listaVecini[nodCurent][i].second;

            if (distanta[nodCurent]+cost<distanta[nodVecin])
                distanta[nodVecin]=distanta[nodCurent]+cost;
        }
    }
}

bool Verificare()
{
    for (int i=1; i<=NrNoduri; i++)
        if (distanta[i]!=distantaPresupusa[i])
            return 0;
    return 1;
}
void Print()
{
    if (Verificare())
        fout << "DA";
    else fout << "NU";
    fout << "\n";
}

int main()
{
    fin >> nrGrafuri;
    for (int i=1; i<=nrGrafuri; i++)
        {
            Read();
            Dijkstra(nodSursaGlobal);
            Print();
        }
    fin.close();
    fout.close();
    return 0;
}