// SPDX-License-Identifier: BSD-3-Clause

import java.io.*;
import java.util.*;

public class Main {
    static class Task {
        public static final String INPUT_FILE = "distante.in";
        public static final String OUTPUT_FILE = "distante.out";

        private static final long INF = 1L << 60; // suficient > dist max
        private final List<String> verdicts = new ArrayList<>();

        public void solve() {
            readInput();
            writeOutput();
        }

        /* ------------------- CITIRE rapidă, stil laborator ------------------- */
        private void readInput() {
            try (BufferedReader br = new BufferedReader(new FileReader(INPUT_FILE))) {
                int T = Integer.parseInt(br.readLine().trim());

                for (int t = 0; t < T; t++) {
                    StringTokenizer st = new StringTokenizer(br.readLine());
                    int N = Integer.parseInt(st.nextToken());
                    int M = Integer.parseInt(st.nextToken());
                    int S = Integer.parseInt(st.nextToken());

                    long[] claimed = new long[N + 1];
                    st = new StringTokenizer(br.readLine());
                    for (int i = 1; i <= N; i++) claimed[i] = Long.parseLong(st.nextToken());

                    int[] head = new int[N + 1];
                    Arrays.fill(head, -1);
                    int[] to   = new int[2 * M];
                    int[] cost = new int[2 * M];
                    int[] nxt  = new int[2 * M];
                    int idx = 0;

                    for (int i = 0; i < M; i++) {
                        st = new StringTokenizer(br.readLine());
                        int u = Integer.parseInt(st.nextToken());
                        int v = Integer.parseInt(st.nextToken());
                        int c = Integer.parseInt(st.nextToken());
                        to[idx] = v; cost[idx] = c; nxt[idx] = head[u]; head[u] = idx++;
                        to[idx] = u; cost[idx] = c; nxt[idx] = head[v]; head[v] = idx++;
                    }

                    long[] dist = dijkstra(N, S, head, to, cost, nxt);

                    boolean ok = true;
                    for (int i = 1; i <= N && ok; i++) {
                        long real = dist[i] >= INF / 2 ? -1 : dist[i];
                        if (real != claimed[i]) ok = false;
                    }
                    verdicts.add(ok ? "DA" : "NU");
                }
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        /* ------------------------- SCRIERE --------------------------- */
        private void writeOutput() {
            try (BufferedWriter bw = new BufferedWriter(new FileWriter(OUTPUT_FILE))) {
                for (String v : verdicts) {
                    bw.write(v);
                    bw.newLine();
                }
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        /* ------------------- Dijkstra cu heap manual ------------------- */
        private static long[] dijkstra(int N, int S, int[] head, int[] to, int[] cost, int[] nxt) {
            long[] dist = new long[N + 1];
            Arrays.fill(dist, INF);
            dist[S] = 0;

            int[] heap = new int[N + 1];
            int[] pos  = new int[N + 1];
            int hsz = 1;
            heap[1] = S; pos[S] = 1;

            while (hsz > 0) {
                int u = heap[1];
                pos[u] = 0;
                heap[1] = heap[hsz--];
                if (hsz > 0) pos[heap[1]] = 1;
                siftDown(heap, pos, dist, hsz, 1);

                for (int e = head[u]; e != -1; e = nxt[e]) {
                    int v = to[e];
                    long nd = dist[u] + cost[e];
                    if (nd < dist[v]) {
                        dist[v] = nd;
                        if (pos[v] == 0) {
                            heap[++hsz] = v;
                            pos[v] = hsz;
                            siftUp(heap, pos, dist, hsz);
                        } else {
                            siftUp(heap, pos, dist, pos[v]);
                        }
                    }
                }
            }
            return dist;
        }

        /* ------------------- Heap utilities ------------------- */
        private static void siftUp(int[] heap, int[] pos, long[] dist, int i) {
            while (i > 1) {
                int p = i >>> 1;
                if (dist[heap[p]] <= dist[heap[i]]) break;
                swap(heap, pos, p, i);
                i = p;
            }
        }

        private static void siftDown(int[] heap, int[] pos, long[] dist, int n, int i) {
            while (true) {
                int l = i << 1, r = l | 1, s = i;
                if (l <= n && dist[heap[l]] < dist[heap[s]]) s = l;
                if (r <= n && dist[heap[r]] < dist[heap[s]]) s = r;
                if (s == i) break;
                swap(heap, pos, i, s);
                i = s;
            }
        }

        private static void swap(int[] heap, int[] pos, int i, int j) {
            int vi = heap[i], vj = heap[j];
            heap[i] = vj; heap[j] = vi;
            pos[vi] = j; pos[vj] = i;
        }
    }

    public static void main(String[] args) {
        new Task().solve();
    }
}