Задача Z3. Тайна самой дальней планеты ≡

Условие

В далёком 2182 году экспедиция с планеты Земля отправляется в космос на поиски Говоруна, что отличается умом и сообразительностью. Проблема в том, что Говоруна похитили пираты с планеты Катрук. По некоторым сведениям известно, что Говорун находится на планете t.

Чтобы быть готовым к худшему сценарию полёта, так как точно неизвестно, как далеко пираты смогли спрятать Говоруна, состав экспедиции во главе с капитаном Зелёным принимает решение рассчитать маршрут максимальной длины — тот, что пройдёт через космические пути, не возвращаясь на уже посещённые планеты. Только зная этот путь, экспедиция поймёт, сколько времени и ресурсов понадобится в самом неблагоприятном случае — и сможет пройти его целиком, если Говорун действительно окажется на самой дальней планете.

Капитан Зеленый предположил, что экспедиция затратит k у.е топлива и решил проверить свои догадки. Помогите капитану понять, сколько у.е топлива не хватит при худшем сценарии, чтобы экспедиция могла подготовиться лучше к предстоящему полёту!

Формат входных данных

Первая строка входного файла содержит Два целых числа n, m — количество планет и переходов между ними.

Вторая строка входного файла содержит два целых чисел k и t - предположительное количество у.е топлива, требуемое эспедиции и планета, на которой находится Говорун.

Далее идут m строк, в каждой из которых указаны три целых числа через пробел:

• u и v — номера планет, которые соединяют переход.
• w — количество топлива, необходимое для перехода между планетами u и v.

Формат выходных данных

Ограничения

n ≤ 100,

0 ≤ m ≤ n².

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

4 6 
15 2
0 2 9
0 3 7
0 1 5
1 3 10
1 2 4
2 3 6

6