**Замечание: время на тест в этой задаче 3 сек, в 1.5 раза больше
чем по умолчанию. Память на тест 512 Мбт, что в два раза больше чем по умолчанию.
Фермер Джон хочет продвинуть свою линию электрических тракторов,
создав рекламную сеть электрозарядных станций. Он подготовил \(N\)
(\(2\le N\le 5\cdot 10^4\)) интересных точек, пронумеровав их \(1\dots N\),
из которых первые \(C\) (\(1\le C < N\)) это зарядные станции, а оставшиеся
- станции для посещения во время рекламного путешествия.
Эти интересные точки соединены (\(1\le M\le 10^5\)) двунаправленными дорогами,
\(i\)-ая из которых соединяет различные точки \(u_i\) и \(v_i\) (\(1\le u_i, v_i\le N\))
и имеет длину \(\ell_i\) миль (\(1\le\ell_i\le 10^9\)).
Электротрактор может путешествовать \(2R\) миль (\(1\le R\le 10^9\)) на
одной зарядке, позволяя достичь любую точку в пределах \(R\) миль от зарядной
станции. Точка назначения считается хорошо-связной, если она достижима
не менее чем из \(K\) (\(1\le K\le 10\)) различных зарядных станций. Ваша задача -
помочь ФД определить множество хорошо связных точек назначения.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит пять разделённых одиночными пробелами целых чисел
\(N\),
\(M\),
\(C\),
\(R\),
\(K\). Каждая из последующих
\(M\) строк содержит три
разделённых одиночными пробелами целых чисел:
\(u_i\),
\(v_i\),
\(\ell_i\)
(
\(u_i\neq v_i\)).
Зарядные станции помечены номерами \(1, 2, \ldots, C\). Оставшиеся точки
это интересные места для посещения.
ФОРМАТ ВЫВОДА (на экран / stdout):
Сначала выведите количество хорошо связных точек назначения в одной строке.
Затем выведите сами хорошо связные точки назначения в возрастающем порядке,
каждую на отдельной строке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 1 4 1
1 2 3
1 3 5
2 3 2
|
1
2
|