Рабочее место участника

В городе есть `N` площадей, соединенных дорогами. Известна длина каждой дороги. Посчитайте количество способов добраться с площади `A` до площади `B` так, чтобы пройденный путь был минимален.

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

Ограничения: `1\ ≤\ N\ ≤\ 1000`, `1\ ≤\ M\ ≤\ 100000`, `1\ ≤\ A\ ≤\ N`, `1\ ≤\ B\ ≤\ N`. Длины улиц выражаются натуральными числами, не превышающими 100000.

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

4 5
1 4 2
1 2 2
3 4 1
2 4 2
1 3 1
1 4

2

5 4
1 2 5
4 5 4
1 3 4
2 3 2
2 5

0