Кількість найкоротших шляхів

Вхідні дані

Перший рядок містить два цілі числа: $N$ (кількість площ у місті) та $M$ (кількість вулиць). Далі йде $M$ рядків, кожен з яких описує вулицю трьома цілими числами: номерами двох площ, які вона з'єднує, та її довжиною. Жодна вулиця не з'єднує площу саму з собою. Ту ж пару площ може з'єднувати декілька вулиць (можливо, різної довжини). Будь-якою вулицею можна скористатися у обох напрямках. Нарешті, задані номери $A$ та $B$.

Обмеження: 1 \leq N \leq 1000, 1 \leq M \leq 100000, 1 \leq A \leq N, 1 \leq B \leq N. Довжини вулиць — додатні цілі числа, не більші за $100000$.

Вихідні дані

Виведіть кількість найкоротших шляхів між площами $A$ і $B$. Якщо дістатися з площі $A$ до $B$ неможливо, виведіть 0.

Приклади