Страна Берляндия состоит из n городов, пронумерованных целыми числами от 1 до n. Некоторые города соединены двунаправленными дорогами, каждая из которых имеет некоторую длину. Из каждого города существует путь в любой другой город по дорогам. Согласно Самым Секретным Документам, Берляндию охраняют Самые Секретные Ракеты. Точное местонахождение Самых Секретных Ракетных Шахт неизвестно, но Вася сумел достать информацию, в которой сказано, что все Шахты расположены точно на расстоянии l от столицы, которая находится в городе номер s.
В документах дано формальное определение: в некотором месте, являющемся городом или точкой на дороге, находится Самая Секретная Ракетная Шахта тогда и только тогда, когда кратчайшее расстояние от этого места до столицы по дорогам страны в точности равно l.
Вася хочет узнать, сколько именно ракетных шахт находится в Берляндии, чтобы затем продать эту информацию вражеским шпионам. Помогите Васе.
Выходные данные
Выведите единственное число — сколько Самых Секретных Ракетных Шахт находится в Берляндии.
Примечание
В первом примере шахты расположены в городах 3 и 4, а также на дороге (1, 3) на расстоянии 2 от города 1 (соответственно, на расстоянии 1 от города 3).
Во втором примере одна из шахт расположена точно на середине дороги (1, 2), а еще две — на дороге (4, 5) на удалении 3 от города 4 в сторону города 5 и на удалении 3 от города 5 в сторону города 4.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 6 1
1 2 1
1 3 3
2 3 1
2 4 1
3 4 1
1 4 2
2
|
3
|
|
2
|
5 6 3
3 1 1
3 2 1
3 4 1
3 5 1
1 2 6
4 5 8
4
|
3
|