P6770 [USACO05MAR] Checking an Alibi Alibi Proof

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.

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.

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

#### 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