Зубры

Это задача про зубров и любые совпадения с бизонами считайте случайными. Страна зубров состоит из N городов, которые соединены M двусторонними дорогами (между двумя городами есть только одна дорога). Известно, что дороги были построены так, что из любого города по дорогам можно добраться до любого другого города.

Зубры Виталя и Рома постоянно играют в одну и ту же игру: Рома загадывает число L, а Виталя должен проверить можно ли из какого-нибудь города добраться до K других городов, если проходить только по дорогам, длина которых не меньше L.

Виталя очень устал, да и скоро ему встречаться с Поликарпом, поэтому он просит вас помочь решить эту задачу раз и навсегда: найдите максимально возможное число L, такое что, существует город из которого можно добраться до K других городов проходя по дорогам, длина которых не меньше L.

Входные данные

Первая строка входного файла INPUT.TXT содержит три целых числа: N (2 ≤ N ≤ 10⁵), M (N-1 ≤ M ≤ min(N*(N-1)/2, 10⁵)) и K (1 ≤ K < N) – общее число городов, число дорог и число городов, до которых нужно добраться.

Следующие M строк содержат по три натуральных числа: a_i, b_i (1 ≤ a_i, b_i ≤ N) и l_i (l_i ≤ 10⁹) – первые два числа задают номера городов, которые соединяет дорога, а третье число – длину дороги.

Гарантируется, что любые два города соединяются не более чем одной дорогой, а так же, что нет дорог, которые соединяют город сам с собой.

Выходные данные

В выходной файл OUTPUT.TXT выведите единственное целое число – ответ на задачу.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!