This question is part of the Competitive Programming 3 book however I haven’t quite reached that chapter yet. Let me see how my approach to solving this problem changes once I get there.

Below is the way I would have done it without having reading the book.

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * 
 * @author Sanchit M. Bhatnagar
 * @see http://uhunt.felix-halim.net/id/74004
 * 
 */
public class P1112 {

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

    int zz = sc.nextInt();
    for (int i = 0; i < zz; i++) {
      if (i != 0)
        out.println();
      int N = sc.nextInt();
      int E = sc.nextInt() - 1;
      int T = sc.nextInt();
      int M = sc.nextInt();
      Node[] graph = new Node[N];
      for (int j = 0; j < N; j++) {
        graph[j] = new Node(j);
      }
      for (int j = 0; j < M; j++) {
        int a = sc.nextInt() - 1;
        int b = sc.nextInt() - 1;
        int c = sc.nextInt();
        graph[a].add(graph[b], c);
      }
      int[] shortest = new int[N];
      for (int j = 0; j < N; j++) {
        if (shortest[j] == 0) {
          Object[] output = dfs(graph, j, E);
          if (output != null) {
            @SuppressWarnings("unchecked")
            ArrayList<Integer> tmp = (ArrayList<Integer>) output[0];
            int cost = (int) output[1];
            int size = tmp.size();
            int thing = 0;
            shortest[tmp.get(0)] = cost;
            for (int k = 1; k < size; k++) {
              thing += graph[tmp.get(k - 1)].cost.get(tmp.get(k));
              shortest[tmp.get(k)] = cost - thing;
            }
          } else {
            shortest[j] = -1;
          }
          for (int k = 0; k < N; k++) {
            graph[k].visited = false;
          }
        }
      }
      int ans = 0;
      for (int j = 0; j < N; j++) {
        if (shortest[j] <= T && shortest[j] != -1) {
          ans++;
        }
      }
      out.println(ans);
    }
    out.close();
    sc.close();
  }

  @SuppressWarnings("unchecked")
  private static Object[] dfs(Node[] graph, int j, int e) {
    PriorityQueue<Object[]> queue = new PriorityQueue<Object[]>(1, new Comparator<Object[]>() {
      @Override
      public int compare(Object[] o1, Object[] o2) {
        return Integer.compare((int) o1[2], (int) o2[2]);
      }
    });
    queue.add(new Object[] { graph[j], new ArrayList<Integer>(), 0 });
    while (!queue.isEmpty()) {
      Object[] next = queue.poll();
      Node n = ((Node) next[0]);
      ((ArrayList<Integer>) next[1]).add(n.idx);
      n.visited = true;
      if (n.idx == e) {
        return new Object[] { next[1], next[2] };
      } else {
        for (Integer in : n.cost.keySet()) {
          if (!graph[in].visited) {
            ArrayList<Integer> tmp = new ArrayList<Integer>();
            tmp.addAll((ArrayList<Integer>) next[1]);
            queue.add(new Object[] { graph[in], tmp, (int) next[2] + n.cost.get(in) });
          }
        }
      }
    }
    return null;
  }

  private static class Node {
    boolean visited;
    int idx;
    HashMap<Integer, Integer> cost;

    public Node(int idx) {
      this.idx = idx;
      cost = new HashMap<Integer, Integer>();
    }

    public void add(Node n, int cost) {
      if (this.cost.containsKey(n.idx)) {
        int tmp = this.cost.get(n);
        this.cost.put(n.idx, Math.min(tmp, cost));
      } else {
        this.cost.put(n.idx, cost);
      }
    }
  }

}