Eninə axtarış 0-1-2

Verilmiş istiqamətsiz qrafda, kənarların çəkisi yalnız 0, 1 və ya 2 ola bilər. s və d zirvələri arasında ən qısa məsafəni tapın.

Giriş məlumatları

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

Çıxış məlumatları

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

Nümunələr