当前没有测试数据。

一、Problem Name

Bessla Motors

二、Problem Description

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\leq N\leq5\cdot10^4$) points of interest labeled $1\cdots N$, of which the first $C$ ($1\leq C<N$) are charging stations and the remainder are travel destinations. These points of interest are interconnected by $M$ ($1\leq M\leq10^5$) bidirectional roads, the $i$th of which connects distinct points $u_i$ and $v_i$ ($1\leq u_i,v_i\leq N$) and has length $\ell_i$ miles ($1\leq\ell_i\leq10^9$).

A Bessla can travel up to $2R$ miles ($1\leq R\leq10^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\leq K\leq10$) distinct charging stations. Your task is to assist Farmer John in identifying the set of well-connected travel destinations.

三、Input Format (input arrives from the terminal / stdin)

1. 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$.
2. The charging stations are labeled $1,2,\cdots,C$. The remaining points of interest are all travel destinations.

四、Output Format (print output to the终端 / stdout)

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

五、Sample Input and Output

Sample Input 1

3 3 1 4 1
1 2 3
1 3 5
2 3 2

Sample Output 1

1
2

Explanation: 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.

Sample Input 2

4 3 2 101 2
1 2 1
2 3 100
1 4 10

Sample Output 2

2
3
4

Explanation: 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.

Sample Input 3

4 3 2 100 2
1 2 1
2 3 100
1 4 10

Sample Output 3

1
4

六、Scoring Rules

1. Inputs 4 and 5: $K = 2$ and $N\leq500$ and $M\leq1000$.
2. Inputs 6 and 7: $K = 2$.
3. Inputs 8 - 15: No additional constraints.

Problem credits: Alexander Wei.