Задача E. Заморозки в Невеции

Автор:А. Щуров   Ограничение времени: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 начисляются за каждый пройденный тест, если тесты необходимых подзадач пройдены.

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
NMwi
1152 ≤ N ≤ 102M = N − 1wi ≤ 103полная
2152 ≤ N ≤ 102M ≤ N(N − 1)2wi ≤ 1031полная
3152 ≤ N ≤ 102M ≤ N(N − 1)2wi ≤ 1091, 2полная
4552 ≤ N ≤ 103M ≤ N(N − 1)2wi ≤ 1091, 2, 3полная

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4 3 5
1 2 15
2 3 11
3 4 20
4
2
2 1 1
1 2 3
2
3
3 3 10
1 2 9
1 3 10
2 3 10
1

0.093s 0.011s 13