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

Условие

Точки города Невеция связаны водными каналами, i-й из которых имеет ширину w_i. Каналы спроектированы так, что из любой точки города можно на лодке попасть в любую другую. Лодка может проплыть по каналу, если её ширина не превосходит ширины канала.

В Невеции ударили морозы, и скоро водные каналы станут ледяными. Физики Невеции обнаружили, что каналы замерзают на один метр в сутки по ширине с каждой стороны, становясь таким образом с каждым днем всё ́́уже.

Транспортной компании Невеции необходимо знать, через сколько дней их лодки шириной W потеряют возможность попасть из любой точки города в любую другую.

Формат входного файла

Входные данные содержат целые числа N, M и W — количество точек города, количество каналов и ширина лодок. Далее следуют M троек целых чисел a_i b_i w_i — точки, которые соединяет канал, и его ширина. Каждый канал описывается ровно один раз.

Формат выходного файла

Выходные данные должны содержать одно целое число.

Ограничения

2 ≤ N ≤ 10³

1 ≤ a_i, b_i ≤ N

1 ≤ M ≤ N(N − 1)2

1 ≤ w_i, W ≤ 10⁹

Описание подзадач и системы оценивания

Баллы за подзадачи 1,2,3 начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены. Баллы за подзадачу 4 начисляются за каждый пройденный тест, если тесты необходимых подзадач пройдены.

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

4 3 5
1 2 15
2 3 11
3 4 20

4

2 1 1
1 2 3

2

3 3 10
1 2 9
1 3 10
2 3 10

1