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

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

public class Main {
    static class Task {
        /* === Fișiere de I/O conform modelului dat === */
        public static final String INPUT_FILE  = "in";
        public static final String OUTPUT_FILE = "out";

        /* === Constante și structuri de date === */
        private static final long INF = Long.MAX_VALUE >>> 2; // ∞ sigur sub overflow

        /** Răspunsurile "DA" / "NU" pentru fiecare graf */
        private final List<String> verdicts = new ArrayList<>();

        /** Execută rezolvarea completă */
        public void solve() {
            readInput();            // populează lista `verdicts`
            writeOutput();          // scrie verdicturile în fișier
        }

        /* ============================================================= */
        /*                         CITIREA DATELOR                       */
        /* ============================================================= */
        private void readInput() {
            try (Scanner sc = new Scanner(new BufferedReader(new FileReader(INPUT_FILE)))) {
                int T = sc.nextInt();                // număr de grafuri

                for (int t = 0; t < T; t++) {
                    int N = sc.nextInt();            // noduri
                    int M = sc.nextInt();            // muchii
                    int S = sc.nextInt();            // sursă

                    /* distanţele declarate de Bronzarel */
                    long[] claimed = new long[N + 1];
                    for (int i = 1; i <= N; i++) {
                        claimed[i] = sc.nextLong();
                    }

                    /* ---- Construim lista de adiacenţă foarte compactă ---- */
                    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 = sc.nextInt();
                        int v = sc.nextInt();
                        int c = sc.nextInt();
                        // muchie u -> v
                        to[idx]   = v;
                        cost[idx] = c;
                        nxt[idx]  = head[u];
                        head[u]   = idx++;
                        // muchie v -> u (graf neorientat)
                        to[idx]   = u;
                        cost[idx] = c;
                        nxt[idx]  = head[v];
                        head[v]   = idx++;
                    }

                    /* ---- Dijkstra cu heap manual ---- */
                    long[] dist = new long[N + 1];
                    Arrays.fill(dist, INF);
                    dist[S] = 0;

                    int[] heap = new int[N + 1]; // 1‑based
                    int[] pos  = new int[N + 1];
                    int heapSz = 1;
                    heap[1] = S;
                    pos[S]  = 1;

                    while (heapSz > 0) {
                        int u = heap[1];
                        pos[u] = 0;
                        heap[1] = heap[heapSz--];
                        if (heapSz > 0) pos[heap[1]] = 1;
                        siftDown(heap, pos, dist, heapSz, 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) {      // nod nou în heap
                                    heap[++heapSz] = v;
                                    pos[v] = heapSz;
                                    siftUp(heap, pos, dist, heapSz);
                                } else {
                                    siftUp(heap, pos, dist, pos[v]);
                                }
                            }
                        }
                    }

                    /* ---- Verificare ---- */
                    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);
            }
        }

        /* ============================================================= */
        /*                         SCRIEREA DATELOR                      */
        /* ============================================================= */
        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);
            }
        }

        /* ============================================================= */
        /*                 HEAP MANUAL – OPERAŢII AJUTĂTOARE            */
        /* ============================================================= */
        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;
                int r = l | 1;
                int smallest = i;
                if (l <= n && dist[heap[l]] < dist[heap[smallest]]) smallest = l;
                if (r <= n && dist[heap[r]] < dist[heap[smallest]]) smallest = r;
                if (smallest == i) break;
                swap(heap, pos, i, smallest);
                i = smallest;
            }
        }

        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();
    }
}