Автор: | А. Щуров | Ограничение времени: | 3 сек | |
Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
Выходной файл: | output.txt | |||
Максимальный балл: | 100 |
Точки города Невеция связаны водными каналами, i-й из которых имеет ширину wi. Каналы спроектированы так, что из любой точки города можно на лодке попасть в любую другую. Лодка может проплыть по каналу, если её ширина не превосходит ширины канала.
В Невеции ударили морозы, и скоро водные каналы станут ледяными. Физики Невеции обнаружили, что каналы замерзают на один метр в сутки по ширине с каждой стороны, становясь таким образом с каждым днем всё ́́уже.
Транспортной компании Невеции необходимо знать, через сколько дней их лодки шириной W потеряют возможность попасть из любой точки города в любую другую.
Входные данные содержат целые числа N, M и W — количество точек города, количество каналов и ширина лодок. Далее следуют M троек целых чисел ai bi wi — точки, которые соединяет канал, и его ширина. Каждый канал описывается ровно один раз.
Выходные данные должны содержать одно целое число.
2 ≤ N ≤ 103
1 ≤ ai, bi ≤ N
1 ≤ M ≤ N(N − 1)2
1 ≤ wi, W ≤ 109
Баллы за подзадачи 1,2,3 начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены. Баллы за подзадачу 4 начисляются за каждый пройденный тест, если тесты необходимых подзадач пройдены.
Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке | ||
---|---|---|---|---|---|---|
N | M | wi | ||||
1 | 15 | 2 ≤ N ≤ 102 | M = N − 1 | wi ≤ 103 | полная | |
2 | 15 | 2 ≤ N ≤ 102 | M ≤ N(N − 1)2 | wi ≤ 103 | 1 | полная |
3 | 15 | 2 ≤ N ≤ 102 | M ≤ N(N − 1)2 | wi ≤ 109 | 1, 2 | полная |
4 | 55 | 2 ≤ N ≤ 103 | M ≤ N(N − 1)2 | wi ≤ 109 | 1, 2, 3 | полная |
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|