Snowfall
Национална Олимпиада по Информатика 2018, Кръг 3
Time Limit: 3s, Memory Limit: 64MiB
Зимата идва. Сега Ели иска да участва във всичко свързано с нея. Едно от тези неща е изчистването на снега от републиканските пътища и градските улици.

В зависимост колко сняг падне, някои от пътищата между градовете стават непроходими. За всеки път Ели знае колко сняг трябва да падне, за да стане блокиран. Градовете са по-сложни. Дори едва да ръсне снежец, всички изведнъж почват да карат като обезумели, в следствие на което стават много катастрофи и се получават огромни задръствания, което блокира движението в града. За щастие, градовете биват чистени от снега и това не се случва.

Някои от снегорините са стари и е възможно съвсем скоро да се развалят. Ако това се случи, градът, където се е случило, ще остане неизчистен и, съответно, блокиран. Нещо повече, управниците на държавата установиха, че ако определен град стане непроходим, е възможно хора от някой неблокиран град да не могат да стигнат до близките си за Коледа в друг неблокиран град, само и единствено защото не могат да минат през блокирания такъв. В този случай гражданите ще бъдат много ядосани и това води до риск управниците да не бъдат избрани на следващите избори.

Управниците дефинират град X като "опасен", ако (след падането на определено количество сняг):
  • Ако никой град не е блокиран, всички градове са достижими един от друг;
  • Ако град X е блокиран, има поне една двойка градове, които не са достижими един от друг.
Забележете, че по горната дефиниция ако два града са недостижими един от друг понеже снегът е блокирал пътища по всички възможни трасета от единия до другия, то тогава НИКОЙ град не е "опасен".

Да се обнови техниката за чистене на снега е много скъпо начинание и управниците ще се съгласят да го направят само ако K или повече от градовете станат "опасни". Сега Ели се чуди какво е минималното количество сняг, което трябва да падне за да се случи това.

Считаме, че когато вали сняг, едно и също количество сняг пада навсякъде в държавата. Когато не е паднал сняг, всички градове са достижими един от друг. Възможно е да има пътища от град до самия себе си (например, околовръстен път), както и няколко пътя между двойка градове (например, магистрала и "стар път"). Всички пътища са двупосочни.
Вход
На първия ред на стандартния вход ще бъдат зададени трите цели числа N, M, и K – съответно броя градове, броя пътища и минималния брой "опасни" градове, които ще доведат до закупуване на ново оборудване. На всеки от следващите M реда ще бъдат зададени три цели числа Ai Bi Si, указващи, че има двупосочен път между градовете Ai и Bi, който ще се блокира ако паднат Si или повече сантиметра сняг.
Изход
На първия ред на стандартния изход изведете две цели числа X и Y – минималното количество сняг, което трябва да падне за да станат "опасни" поне K града, и колко всъщност града са "опасни" при това количество сняг. На следващия ред изведете Y цели числа, сортирани в нарастващ ред – номерата на градовете, които са опасни при X сантиметра сняг. Ако никакво количество сняг не води до K или повече опасни града, изведете X = -1 и Y = 0.
Ограничения
  • 2 ≤ N ≤ 50,000
  • 1 ≤ M ≤ 200,000
  • 1 ≤ KN
  • 1 ≤ Ai, BiN
  • 1 ≤ Si ≤ 1,000,000,000
Примерен Вход Примерен Изход
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 града, свързани чрез 13 пътя. Управниците на страната ще подновят оборудването ако се получат 3 или повече опасни града. Първият блокиран път се получава с 5 сантиметра сняг, но дори без него все още няма "опасни" градове. Със 7 сантиметра сняг още един път става неизползваем, и с това се появява и първият "опасен" град – град 3. Ако той стане блокиран, градовете 5 и 8 вече не могат да бъдат достигнати от останалите. Управниците на държавата не ги трогва наличието на само един опасен град, така че трябва да падне още сняг. Следващият блокиран път се случва при 8 сантиметра сняг. Това променя нещата драстично, като така градовете 1, 2, 3, и 7 са "опасни". Това вече е доста над максимума от 2 града, които те считат за приемлива бройка, затова те трябва да купят новото оборудване.

Във втория пример при каквото и да е количество сняг по-малко от 42 никой град няма да бъде опасен. С 42 или повече пък град 2 става изолиран от останалите, което означава, че ще има двойка недостижими един от друг градове независимо дали някой от градовете е блокиран или не.
Мрън!