Страну Берляндию можно представить как неориентированный граф с $$$n$$$ вершинами с $$$m$$$ ребрами, где вершины соответствуют городам, а ребра – двусторонним дорогам, соединяющим города. Дорога с номером $$$i$$$ ($$$1 \le i \le m$$$) соединяет города с номерами $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$) и имеет $$$\textit{эффективность}$$$ $$$c_i$$$. Эффективность дороги – численная характеристика, описывающая сколько миллиметров снега может выпасть на нее прежде, чем по ней невозможно будет проехать. Берляндия очень маленькая, поэтому когда идет снег, можно считать, что на все дороги выпадает одинаковое количество миллиметров снега.
Назовем город $$$i$$$ $$$\textit{опасным}$$$ при выпадении на дороги $$$C$$$ миллиметров снега, если выполнены следующие два условия:
Совсем недавно в Берляндии вышел указ, в котором сообщалось, что если в какой-то момент времени одновременно будет $$$k$$$ или более опасных городов, то на обсуждение будет вынесен вопрос о реструктуризации системы дорог. После этой новости городским активистам стало интересно, какое минимальное количество снега должно выпасть, чтобы по крайней мере $$$k$$$ городов стали опасными. Именно на этот вопрос Вам и предстоит ответить.
$$$\textbf{Известно, что изначально все города образуют связный граф.}$$$
Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$2 \le n \le 5 \cdot 10^4$$$, $$$1 \le m \le 2 \cdot 10^5$$$, $$$1 \le k \le n$$$) — количество городов, количество дорог и минимальное количество опасных городов, которое необходимо для проведения реструктуризации системы дорог.
Следующие $$$m$$$ строк содержат описания дорог — три целых числа $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$1 \le c_i \le 10^9$$$) — номера городов, соединенных дорогой, и эффективность дороги. Обратите внимание, что между одной парой городов может быть более одной дороги, а также дорога может соединять город с самим собой.
В первой строке выведите два целых числа $$$X$$$ и $$$Y$$$, разделенных пробелом — минимальное количество миллиметров снега, которое должно выпасть, чтобы по крайней мере $$$k$$$ городов стали опасными, и сколько на самом деле городов опасны при таком количестве снега.
В следующей строке выведите $$$Y$$$ целых чисел, отсортированных в порядке возрастания, — номера городов, представляющих опасность при условии, что выпало $$$X$$$ миллиметров снега. Если никакое количество снега не приводит к ситуации, когда $$$k$$$ или более городов являются опасными, выведите $$$X = -1$$$ и $$$Y = 0$$$.
8 13 3 1 2 19 1 3 13 2 3 5 4 2 9 2 5 7 3 5 17 6 3 8 3 8 12 4 7 11 5 7 5 7 2 10 7 6 13 8 5 16
8 4 1 2 3 7
3 3 1 1 2 42 2 3 42 1 3 666
-1 0
В первом примере, если на дороги выпадет $$$8$$$ миллиметров снега, то города все еще будут представлять связный граф. При удалении одного любого города среди городов с номерами $$$1, 2, 3, 7$$$ граф перестанет быть связным.
Во втором примере, если на дороги выпадет $$$42$$$ миллиметров снега, то города в номерами $$$1$$$ и $$$2$$$ перестанут быть достижимыми друг из друга. По первому условию определения опасности города получаем, что никакой город не является опасным.