Bessla Motors

Time limit3sMemory limit1024 MB

Summary

Find the travel destinations within R miles of at least K distinct charging stations on a weighted road graph, then print their count and list them in ascending order.

Level: Medium6 of 10
Topics: Shortest path, Graph, Heap
Solved: No attempts yet

Problem

Farmer John wants to promote his line of Bessla electric tractors by showing off Bessla's network of charging stations. There are $N$ ( $2\le N\le 5\cdot 10^4$ ) points of interest labeled $1\dots N$ . The first $C$ ( $1\le C < N$ ) points are charging stations, and the rest are travel destinations. The points are connected by $M$ ( $1\le M\le 10^5$ ) bidirectional roads. The $i$ -th road 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, which lets it reach any destination within $R$ miles of a charging station. A destination is well-connected if it can be reached from at least $K$ ( $1\le K\le 10$ ) distinct charging stations. Find the set of well-connected travel destinations.

Input

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$ , where $u_i\neq v_i$ .

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

Output

First, print the number of well-connected travel destinations on a single line. Then print all of them in ascending order, one per line.

Examples3

Example 1
Input
```
3 3 1 4 1
1 2 3
1 3 5
2 3 2
```
Expected output
```
1
2
```
Example 2
Input
```
4 3 2 101 2
1 2 1
2 3 100
1 4 10
```
Expected output
```
2
3
4
```
Example 3
Input
```
4 3 2 100 2
1 2 1
2 3 100
1 4 10
```
Expected output
```
1
4
```