Genişlik üzrə axtarış 0-1

Verilmiş istiqamətsiz qrafda, kənarların çəkisi yalnız $0$ və ya $1$ ola bilər. Sizdən $s$ və $d$ zirvələri arasında ən qısa məsafəni tapmağınız tələb olunur.

Giriş verilənləri

Birinci sətir dörd tam ədəd ehtiva edir: zirvələrin sayı $n$, kənarların sayı $m(n,m\le 10^5)$ və zirvələrin nömrələri $s$ və $d(1\le s,d\le n)$. Sonrakı $m$ sətirin hər biri üç tam ədəd $a,b$ və $w$ ehtiva edir ki, bu da çəkisi $w(0\le w\le 1)$ olan istiqamətsiz kənar $(a,b)$-ni göstərir.

Çıxış verilənləri

$s$ və $d$ zirvələri arasında ən qısa yolu tapın və göstərin.

Nümunələr