Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Зубры

(Время: 2 сек. Память: 16 Мб Сложность: 51%)

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

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

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

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

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

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

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

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

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

Примеры

INPUT.TXTOUTPUT.TXT
13 3 2
1 2 2
3 2 3
3 1 1
2
24 6 3
1 3 9
3 2 3
1 2 2
4 3 9
2 4 8
1 4 3
8

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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 A. Яблоки
 B. Пирамида
 C. Маги
 D. Зубры
 E. Коллекция
 F. За стол!
 G. Фермер Тетракарп
 H. Саша и массив
 I. Гена атакует
 J. Длина числа

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru