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≤N≤5⋅104) points of interest labeled 1…N, of which the first C (1≤C<N) are charging stations and the remainder are travel destinations. These points of interest are interconnected by M (1≤M≤105) bidirectional roads, the i-th of which connects distinct points ui and vi (1≤ui,vi≤N) and has length ℓi miles (1≤ℓi≤109).
A Bessla can travel up to 2R miles (1≤R≤109) 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≤K≤10) distinct charging stations. Your task is to assist Farmer John in identifying the set of well-connected travel destinations.
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.
SCORING:
- Inputs 4 and 5: K=2 and N≤500 and M≤1000.
- Inputs 6 and 7: K=2.
- Inputs 8-15: No additional constraints.
Problem credits: Alexander Wei
Source: USA Computing Olympiad.
Input Format
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 ui, vi, and ℓi such that ui=vi.
The charging stations are labeled 1,2,…,C. The remaining points of interest are all travel destinations.
Output Format
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.