eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Количество кратчайших путей

Количество кратчайших путей

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

В городе есть N площадей, соединённых дорогами. Известна длина каждой дороги.

Посчитайте количество способов добраться с площади A до площади B так, чтобы пройденный путь был минимален.

Входные данные

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

Ограничения: 1N1000, 1M100000, 1AN, 1BN. Длины улиц выражаются натуральными числами, не превышающими 100000.

Выходные данные

Выведите количество кратчайших путей между площадями A и B. Если с площади A нельзя добраться до площадиB, выведите 0.

Пример

Входные данные #1
4 5
1 4 2
1 2 2
3 4 1
2 4 2
1 3 1
1 4
Выходные данные #1
2