Background

Note: The time limit for this problem is 3 seconds, which is 1.5 times the usual limit. The memory limit for this problem is 512MB, which is 2 times the usual limit.

Problem Description

To promote his Bessla electric tractor series, Farmer John wants to showcase Bessla's charging network. He has marked $N$ ($2 \le N \le 5 \cdot 10^4$) points of interest on the map, numbered $1 \ldots N$, where the first $C$ ($1 \le C < N$) are charging stations and the rest are tourist destinations. These points are connected by $M$ ($1 \le M \le 10^5$) bidirectional roads, where the $i$-th road connects different points $u_i$ and $v_i$ ($1 \le u_i, v_i \le N$) with a length of $l_i$ miles ($1 \le l_i \le 10^9$).

A Bessla tractor 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 considered accessible if it can be reached from at least $K$ ($1 \le K \le 10$) different charging stations. Your task is to help Farmer John determine the set of accessible tourist destinations.

Input Format

The first line of input contains five space-separated integers $N$, $M$, $C$, $R$, and $K$. The following $M$ lines each contain three space-separated integers $u_i$, $v_i$, and $l_i$, where $u_i \neq v_i$.

The charging stations are numbered $1, 2, \ldots, C$. The remaining points of interest are tourist destinations.

Output Format

First, output a line containing the number of accessible tourist destinations. Then, output all accessible tourist destinations in ascending order, each on a new 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

Sample Input #2

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

Sample Output #2

2
3
4

Sample Input #3

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

Sample Output #3

1
4

Notes

Explanation of Sample 1

We have one charging station at point $1$. From this station, we can reach point $2$ (as it is $3$ miles away) but not point $3$ (as it is $5$ miles away). Therefore, only point $2$ is accessible.

Explanation of Sample 2

We have charging stations at points $1$ and $2$, and both points $3$ and $4$ are within $101$ miles of both stations. Therefore, both points $3$ and $4$ are accessible.

Test Case Properties

• Test cases $4-5$: $K=2$, $N \le 500$ and $M \le 1000$.
• Test cases $6-7$: $K=2$.
• Test cases $8-15$: No additional restrictions.

见题面 Input 部分

见题面 Output 部分