README.md

Task 3. Скорости (Medium)

HackerRank link

Statement:

Знаете ли, че движението на автомобили с прекалено ниска скорост може също да затрудни движението и дори да доведе до пътно транспортно произшествие? За да се избегне това, наскоро беше решено да се въведе "минимална скорост" на движение по по-важните пътни артерии – тоест скорост, под която автомобилите не трябва да карат.

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

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

За всеки от пътищата е направено изследване колко е "оптималната" скорост $S_i$ за движение по него. Ако политиците изберат максималната скорост да е под $S_i$ или минималната да е над $S_i$, то пътят става неизползваем. Сега те се чудят какви да бъдат разрешените скорости, така че все пак да е възможно да се стигне от всяко населено място до всяко друго.

Input Format

На първия ред на стандартния вход ще бъдат зададени целите числа $N$ и $M$ – броя населени места и броя пътища.

Следват $M$ на брой реда, всеки съдържащ по три цели числа $F_i, T_i, S_i$, указващи съответно двупосочен път между $F_i$ и $T_i$ с оптимална скорост $S_i$. Възможно е да има по повече от един директен път между две населени места.

Гарантирано е, че ще съществува път между всеки две населени места.

Constraints

$2\le N\le 10^3$

$1\le M\le 10^4$

$1\le F_i, T_i\le N$

$1\le S_i\le 3\cdot10^4$

Output Format

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

Ако съществува повече от един възможен отговор, изведете този с най-ниска минимална (а съответно и максимална) скорост.

---

Sample Input 0

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

Sample Output 0

3 7