Ən qısa yolların sayı

Giriş

Birinci sətirdə iki tam ədəd verilir: $N$ (şəhərdəki meydanların sayı) və $M$ (küçələrin sayı). Sonra $M$ sətir gəlir, hər biri bir küçəni təsvir edir və üç tam ədəd ehtiva edir: o küçənin birləşdirdiyi iki meydanın nömrəsi və uzunluğu. Heç bir küçə bir meydanı özünə birləşdirmir. Eyni iki meydan bir-birinə bir neçə küçə ilə, fərqli uzunluqlarla da bağlana bilər. Hər bir küçədən hər iki istiqamətdə istifadə etmək olar. Sonda $A$ və $B$ meydanlarının nömrələri verilir.

Məhdudiyyətlər: 1 \leq N \leq 1000, 1 \leq M \leq 100000, 1 \leq A \leq N, 1 \leq B \leq N. Küçələrin uzunluğu $100000$-dən çox olmayan müsbət tam ədədlərdir.

Çıxış

$A$ və $B$ meydanları arasında ən qısa yolların sayını çıxışa verin. Əgər $A$-dan $B$-yə çatmaq mümkün deyilsə, 0 çap edin.

Nümunələr