// 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; // sigur > 1e3*5e4
        private final StringBuilder outSB = new StringBuilder();

        public void solve() {
            try (FastReader fr = new FastReader(INPUT_FILE)) {
                int T = fr.nextInt();

                for (int t = 0; t < T; t++) {
                    int N = fr.nextInt();
                    int M = fr.nextInt();
                    int S = fr.nextInt();

                    long[] claimed = new long[N + 1];
                    for (int i = 1; i <= N; i++) claimed[i] = fr.nextLong();

                    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++) {
                        int u = fr.nextInt();
                        int v = fr.nextInt();
                        int c = fr.nextInt();
                        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;
                    }
                    outSB.append(ok ? "DA" : "NU").append('\n');
                }
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            // scriem rezultatul
            try (BufferedWriter bw = new BufferedWriter(new FileWriter(OUTPUT_FILE))) {
                bw.write(outSB.toString());
            } 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 utils ------------------- */
        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; }

        /* ------------------- FastReader intern ------------------- */
        private static class FastReader implements Closeable {
            private static final int BUF = 1 << 16;
            private final byte[] buf = new byte[BUF];
            private final DataInputStream din;
            private int ptr, len;
            FastReader(String file) throws IOException { din = new DataInputStream(new FileInputStream(file)); }
            private int read() throws IOException { if (ptr == len) { len = din.read(buf); ptr = 0; if (len == -1) return -1;} return buf[ptr++]; }
            int nextInt() throws IOException { int c; while ((c = read()) <= ' '); boolean neg=false; if(c=='-'){neg=true; c=read();} int x=0; while(c>' '){ x=x*10+(c-'0'); c=read(); } return neg?-x:x; }
            long nextLong() throws IOException { int c; while ((c = read()) <= ' '); boolean neg=false; if(c=='-'){neg=true;c=read();} long x=0; while(c>' '){ x=x*10+(c-'0'); c=read(); } return neg?-x:x; }
            @Override public void close() throws IOException { din.close(); }
        }
    }

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