침공

외계인의 침공이 시작되었다. 사람을 잡아먹는 무시무시한 외계인들이 전국 곳곳에 기지를 세우고 있다. 당신은 현재 존재하는 모든 외계인 기지로부터 충분히 멀리 떨어진 곳에서만 안전하다. 어디로 피신해야 할지 빠르게 판단할 수 있도록, 안전하게 남아 있는 도시의 수를 구하는 프로그램을 작성하라.

입력은 여러 개의 인스턴스로 이루어지며, 각 인스턴스는 여러 줄에 걸쳐 주어진다. 인스턴스의 첫 줄에는 공백으로 구분된 네 정수 $N$, $M$, $A$, $K$가 주어진다. 각각 나라 안의 도시 수, 도시들을 잇는 도로의 수, 외계인이 세울 기지의 수, 그리고 외계인 기지로부터 지켜야 하는 최소 안전 거리를 뜻한다. 도시에는 $1, \dots, N$의 번호가 매겨져 있다.

• $1 \le N \le 10000$
• $0 \le M \le 100000$
• $0 \le A \le N$
• $1 \le K \le 100$

이어지는 $M$개의 줄은 각각 하나의 도로를 나타내며, 세 정수 $T_1$, $T_2$ ($1 \le T_1 < T_2 \le N$)와 $D$ ($1 \le D \le 100$)가 주어진다. $D$는 도시 $T_1$과 $T_2$를 잇는 도로의 길이다. 임의의 두 도시 사이를 직접 잇는 도로는 최대 하나이며, 모든 도로는 양방향으로 통행할 수 있다.

그다음 $A$개의 줄은 각각 하나의 기지 위치를 나타내며, $i$번째 줄에는 외계인이 $i$번째 기지를 세우는 도시의 번호 $B_i$ ($1 \le B_i \le N$)가 주어진다.

각 인스턴스 뒤에는 빈 줄이 하나 온다. 마지막 인스턴스의 빈 줄 다음에는 네 개의 0이 적힌 줄이 오는데, 이 줄은 어떤 인스턴스에도 속하지 않는다.

각 인스턴스마다 $A$개의 줄을 출력한다. $i$번째 줄에는 외계인이 $i$번째 기지를 세운 뒤 안전한 도시의 수를 출력한다. 어떤 도시가 안전하다는 것은, 그 도시에서 기지 $B_1, B_2, \dots, B_i$ 각각까지의 (도로를 따라 잰) 최단 거리가 모두 $K$ 이상이라는 뜻이다. 어떤 기지에서도 도달할 수 없는 도시는 그 기지에 대해 안전한 것으로 본다.

연속한 두 인스턴스의 출력 블록 사이에는 빈 줄을 하나 넣어 구분한다. 마지막 인스턴스 뒤에는 빈 줄을 출력하지 않으며, 출력은 마지막 줄을 끝내는 개행 문자로 끝난다.