Кількість найкоротших шляхів
У місті є 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.