| Codeforces Round 103 (Div. 2) |
|---|
| Закончено |
Страна Берляндия состоит из n городов, пронумерованных целыми числами от 1 до n. Некоторые города соединены двунаправленными дорогами, каждая из которых имеет некоторую длину. Из каждого города существует путь в любой другой город по дорогам. Согласно Самым Секретным Документам, Берляндию охраняют Самые Секретные Ракеты. Точное местонахождение Самых Секретных Ракетных Шахт неизвестно, но Вася сумел достать информацию, в которой сказано, что все Шахты расположены точно на расстоянии l от столицы, которая находится в городе номер s.
В документах дано формальное определение: в некотором месте, являющемся городом или точкой на дороге, находится Самая Секретная Ракетная Шахта тогда и только тогда, когда кратчайшее расстояние от этого места до столицы по дорогам страны в точности равно l.
Вася хочет узнать, сколько именно ракетных шахт находится в Берляндии, чтобы затем продать эту информацию вражеским шпионам. Помогите Васе.
В первой строке находятся три целых числа n, m и s (2 ≤ n ≤ 105, 
, 1 ≤ s ≤ n) — количество городов, дорог в стране и номер столицы соответственно. Далее в m строках даны описания дорог, каждая из которых описывается тремя целыми числами vi, ui, wi (1 ≤ vi, ui ≤ n, vi ≠ ui, 1 ≤ wi ≤ 1000), где vi, ui — номера городов, которые соединяет эта дорога, а wi — ее длина. Последняя строка входных данных содержит целое число l (0 ≤ l ≤ 109) — расстояние от столицы до ракетных шахт. Гарантируется, что:
- между любыми двумя городами существует не более одной дороги;
- каждая дорога соединяет два различных города;
- из каждого города существует хотя бы один путь в любой другой город по дорогам.
Выведите единственное число — сколько Самых Секретных Ракетных Шахт находится в Берляндии.
4 6 1
1 2 1
1 3 3
2 3 1
2 4 1
3 4 1
1 4 2
2
3
5 6 3
3 1 1
3 2 1
3 4 1
3 5 1
1 2 6
4 5 8
4
3
В первом примере шахты расположены в городах 3 и 4, а также на дороге (1, 3) на расстоянии 2 от города 1 (соответственно, на расстоянии 1 от города 3).
Во втором примере одна из шахт расположена точно на середине дороги (1, 2), а еще две — на дороге (4, 5) на удалении 3 от города 4 в сторону города 5 и на удалении 3 от города 5 в сторону города 4.
