Description

Grain has been found stolen from the barn! FJ is trying to find the criminal who stole the grain among $C$ cows. Luckily, a satellite passing by took a picture of the farm $M$ seconds before the grain was stolen. This allows John to determine who had enough time to steal the grain based on the cows' positions.

John's farm has $F$ fields, numbered from $1$ to $F$, and $P$ bidirectional roads connecting them. The travel time along these roads ranges from $1$ to $7\times 10^4$ seconds. The stolen barn is located on field $1$. Given the farm map and each cow's position in the satellite photo, determine which cows could be guilty.

Note: The testdata may contain multiple edges (edges with the same start and end).

A “cow that could be guilty” means a cow that can reach field $1$ from its position in the photo within $M$ seconds.

Input Format

Line $1$: Four space-separated integers: $F, P, C,$ and $M$.

Lines $2$ to $P+1$: Three space-separated integers describing a road. The road connects $F_1$ and $F_2$ and takes $T$ seconds to travel.

Lines $P+2$ to $P+C+1$: Each line contains one integer, the position of a cow.

Output Format

Line $1$: Output the number of suspects. Then, output one suspect cow index per line, sorted in increasing order.

7 6 5 8
1 4 2
1 2 1
2 3 6
3 5 5
5 4 6
1 7 9
1
4
5
3
7

4
1
2
3
4

Hint

Data Specification

For $100\%$ of the testdata: $1 \le M \le 7\times 10^4$, $1 \le C \le 100$, $1 \le P \le 1000$, $1 \le F \le 500$.

Translated by ChatGPT 5