Ən qısa yolların sayı
Şəhərdə N meydan var və bu meydanlar yollarla birləşdirilib. Hər yolun uzunluğu məlumdur.
Sizdən tələb olunur ki, A meydanından B meydanına minimal məsafə ilə çatmağın neçə fərqli yolu olduğunu hesablayasınız.
Giriş verilənləri
İlk olaraq, şəhərdəki meydanların sayı N və küçələrin sayı M verilir. Daha sonra küçələrin təsviri təqdim olunur. Hər küçə üç ədəd ilə təsvir edilir: birləşdirdiyi meydanların nömrələri və həmin küçənin uzunluğu. Heç bir küçə öz-özünə birləşmir. Eyni meydanlar müxtəlif küçələrlə birləşdirilə bilər və bu küçələrin uzunluqları fərqli ola bilər. Hər küçədən həm irəli, həm də geri istiqamətdə istifadə etmək mümkündür. Son olaraq, A və B meydanlarının nömrələri verilir.
Məhdudiyyətlər: 1 ≤ N ≤ 1000, 1 ≤ M ≤ 100000, 1 ≤ A ≤ N, 1 ≤ B ≤ N. Küçələrin uzunluğu 100000-i keçməyən natural ədədlərlə ifadə olunur.
Çıxış verilənləri
A və B meydanları arasında ən qısa yolların sayını çıxarın. Əgər A meydanından B meydanına çatmaq mümkün deyilsə, 0 çıxarın.