1112 Mouse Race

/*
 * 1112 Mice and Maze
 *
 * Author: John Bowers
 *   Date: ##/##/2015
 */

import java.util.*;

class Main {

    class Edge {
      Node dest;
      int time;
      public Edge(Node dest, int time) { this.dest = dest; this.time = time; }
    }

    public int nodes_reached = 0;

    class Node {
      ArrayList<Edge> adj = new ArrayList<Edge>();
      boolean visited = false;
      int node_id;
      public Node(int node_id) { this.node_id = node_id; }
    }

    class NodePair {
      Node node; int time;
      public NodePair(Node n, int t) { this.node = n; this.time = t; }
      public String toString() { return "(Node: " + (node.node_id+1) + ", " + time + ")"; }
    }

    public Main(Scanner in) {
      int N = in.nextInt(); in.nextLine();
      int E = in.nextInt() - 1; in.nextLine();
      int T = in.nextInt(); in.nextLine();
      int M = in.nextInt(); in.nextLine();

      // Create the nodes:
      Node[] nodes = new Node[N];
      for (int i = 0; i < N; i++) {
        nodes[i] = new Node(i);
      }

      // Read in the edges (flipping them)
      for (int i = 0; i < M; i++) {
        int a = in.nextInt() - 1;
        int b = in.nextInt() - 1;
        int t = in.nextInt(); in.nextLine();

        nodes[b].adj.add(new Edge(nodes[a], t));
      }

      PriorityQueue<NodePair> pq = new PriorityQueue<NodePair>(N,
        new Comparator<NodePair>() {
          public int compare(NodePair p, NodePair q) {
            return p.time - q.time;
          }
        });

      NodePair np = new NodePair(nodes[E], 0);
      pq.add(np);
      System.err.println("PUSH: " + np);

      while (!pq.isEmpty()) {
        NodePair p = pq.remove();
        System.err.println("POP: " + p);
        if (!p.node.visited) {
          nodes_reached ++;
          p.node.visited = true;
          for (Edge e : p.node.adj) {
            if (!e.dest.visited && p.time + e.time <= T) {
              np = new NodePair(e.dest, p.time + e.time);
              System.err.println("PUSH: " + np);
              pq.add(np);
            }
          }
        }
      }
      System.out.println(nodes_reached);
    }

    public static void main(String[] args) {
      Scanner in = new Scanner(System.in);

      int cases = in.nextInt();
      in.nextLine();
      in.nextLine();

      for (int i = 0; i < cases; i++) {
        new Main(in);
        if (i < cases - 1) System.out.println();
      }
    }
}