Количество кратчайших путей
В городе есть N площадей, соединённых дорогами. Известна длина каждой дороги.
Посчитайте количество способов добраться с площади A до площади B так, чтобы пройденный путь был минимален.
Входные данные
Задано число N - количество площадей в городе и M - количество улиц. Далее идёт описание улиц. Каждая улица задаётся тремя числами: номерами площадей, которые она соединяет, и длиной. Никакая улица не соединяет площадь с самой собой. Одни и те же площади могут быть соеденены разными улицами (в том числе, эти улицы могут иметь разную длину). По каждой улице можно ездить как в прямом, так и в обратном направлении. Далее заданы числа A и B.
Ограничения: 1 ≤ N ≤ 1000, 1 ≤ M ≤ 100000, 1 ≤ A ≤ N, 1 ≤ B ≤ N. Длины улиц выражаются натуральными числами, не превышающими 100000.
Выходные данные
Выведите количество кратчайших путей между площадями A и B. Если с площади A нельзя добраться до площадиB, выведите 0.