Speed
Зимни Състезания по Информатика, 2014
Time Limit: 1.2s, Memory Limit: 64MiB
Знаете ли, че движението на автомобили с прекалено ниска скорост може също да затрудни движението и дори да доведе до пътно транспортно произшествие? За да се избегне това, в държавата, където живее Ели, наскоро беше решено да се въведе "минимална скорост" на движение по по-важните пътни артерии – тоест скорост, под която автомобилите не трябва да карат.

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

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

За всеки от пътищата е направено изследване колко е "оптималната" скорост Si за движение по него. Ако политиците изберат максималната скорост да е под Si или минималната да е над Si, то пътят става неизползваем. Сега те се чудят какви да бъдат разрешените скорости, така че все пак да е възможно да се стигне от всяко населено място до всяко друго.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N и M – броя населени места и броя пътища. Следват M на брой реда, всеки съдържащ по три цели числа Fi Ti Si, указващи, съответно, двупосочен път между Fi и Ti с оптимална скорост Si. Възможно е да има по повече от един директен път между две населени места. Гарантирано е, че ще съществува път между всеки две населени места.
Изход
На единствен ред на стандартния изход изведете две цели числа – минималната и максималната разрешена скорост, които хем са възможно най-близки, хем разрешават пътуването между всеки две населени места. Ако съществува повече от един възможен отговор, изведете този с най-ниска минимална (а съответно и максимална) скорост.
Ограничения
  • 2 ≤ N ≤ 1,000
  • 1 ≤ М ≤ 10,000
  • 1 ≤ Fi, TiN
  • 1 ≤ Si ≤ 30,000
Примерен Вход Примерен Изход
7 10 1 3 2 4 2 8 1 2 11 1 4 3 1 3 6 5 3 5 3 6 9 7 6 6 5 6 3 2 5 7 3 7
Минималната разлика в скоростите е 4. Има два възможни отговора: (3, 7) и (5, 9). От тях избираме този с най-ниски скорости - в случая това е двойката (3, 7).
Мрън!