/* * To change this template, choose Tools | Templates * and open the template in the editor. */ import java.io.BufferedReader; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.StringTokenizer; import static java.lang.System.out; /** * * @author cteam059 */ public class invasion { private static class Node implements Comparable { public boolean safe = true; public boolean closed = false; public int distance = Integer.MAX_VALUE; private int index; public List edges = new ArrayList(); public Node(int index) { this.index = index; } public int compareTo(Node n) { return distance - n.distance; } } private static class Edge { Node to; int distance; public Edge(Node to, int distance) { this.to = to; this.distance = distance; } } public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); while (true) { String line = br.readLine(); StringTokenizer tokenizer = new StringTokenizer(line); int nodeCount = 0; if(tokenizer.hasMoreTokens()) nodeCount = Integer.parseInt(tokenizer.nextToken()); int edgeCount = 0; if(tokenizer.hasMoreTokens()) edgeCount = Integer.parseInt(tokenizer.nextToken()); int baseCount = 0; if(tokenizer.hasMoreTokens()) baseCount = Integer.parseInt(tokenizer.nextToken()); int safeDistance = 0; if(tokenizer.hasMoreTokens()) safeDistance = Integer.parseInt(tokenizer.nextToken()); if (nodeCount == 0 && edgeCount == 0 && baseCount == 0 && safeDistance == 0) { return; } Node[] nodes = new Node[nodeCount]; int safeNodeCount = nodeCount; for (int i = 0; i < nodes.length; i++) { nodes[i] = new Node(i); } for (int i = 0; i < edgeCount; i++) { line = br.readLine(); tokenizer = new StringTokenizer(line); int from = 1; if(tokenizer.hasMoreTokens()) from = Integer.parseInt(tokenizer.nextToken()); int to = 1; if(tokenizer.hasMoreTokens()) to = Integer.parseInt(tokenizer.nextToken()); int distance = 0; if(tokenizer.hasMoreTokens()) distance = Integer.parseInt(tokenizer.nextToken()); nodes[from-1].edges.add(new Edge(nodes[to-1], distance)); nodes[to-1].edges.add(new Edge(nodes[from-1], distance)); } for (int i = 0; i < baseCount; i++) { //if (i > 0) { for (int j = 0; j < nodes.length; j++) { nodes[j].closed = false; nodes[j].distance = Integer.MAX_VALUE; } //} int base = Integer.parseInt(br.readLine()); List openList = new ArrayList(); openList.add(nodes[base-1]); nodes[base-1].distance = 0; while (!openList.isEmpty()) { Collections.sort(openList); Node expand = openList.remove(0); expand.closed = true; if(expand.distance < safeDistance) { if(expand.safe) { expand.safe = false; safeNodeCount--; } } else { continue; } for (Edge edge : expand.edges) { if(!edge.to.closed) { edge.to.distance = Math.min(expand.distance + edge.distance, edge.to.distance); openList.add(edge.to); } } } out.println(safeNodeCount); } out.println(); br.readLine(); } } }