Bessla Motors

Note: The time limit for this problem is 3s, 1.5x the default. The memory limit for this problem is 512MB, twice the default.

Farmer John would like to promote his line of Bessla electric tractors by showcasing Bessla's network of charging stations. He has identified $N$ ($2\le N\le 5\cdot 10^4$) points of interest labeled $1\dots N$, of which the first $C$ ($1\le C < N$) are charging stations and the remainder are travel destinations. These points of interest are interconnected by $M$ ($1\le M\le 10^5$) bidirectional roads, the $i$-th of which connects distinct points $u_i$ and $v_i$ ($1\le u_i, v_i\le N$) and has length $\ell_i$ miles ($1\le\ell_i\le 10^9$).

A Bessla can travel up to $2R$ miles ($1\le R\le 10^9$) on a single charge, allowing it to reach any destination within $R$ miles of a charging station. A destination is deemed well-connected if it is reachable from at least $K$ ($1\le K\le 10$) distinct charging stations. Your task is to assist Farmer John in identifying the set of well-connected travel destinations.

The first line contains five space-separated integers $N$, $M$, $C$, $R$, and $K$. Each of the following $M$ lines contains three space-separated integers $u_i$, $v_i$, and $\ell_i$ such that $u_i\neq v_i$.

The charging stations are labeled $1, 2, \ldots, C$. The remaining points of interest are all travel destinations.

• Inputs 4 and 5: $K = 2$ and $N \le 500$ and $M\le 1000$.
• Inputs 6 and 7: $K = 2$.
• Inputs 8-15: No additional constraints.

First, output the number of well-connected travel destinations on a single line. Then, list all well-connected travel destinations in ascending order, each on a separate line.

We have one charging station at $1$. From this charging station, we can reach point $2$ (since it is distance $3$ away from $1$), but not point $3$ (since it is distance $5$ away from $1$). Thus, only point $2$ is well-connected.

We have charging stations at $1$ and $2$, and both points $3$ and $4$ are within distance $101$ of both $1$ and $2$. Thus, both points $3$ and $4$ are well-connected.