Ən qısa yol

Verilmiş istiqamətsiz çəkili qrafda iki zirvə arasında ən qısa yolu tapın.

Giriş şərtləri

Birinci sətir n və m təbii ədədlərini (n ≤ 2000, m ≤ 50000) - qrafın zirvələrinin və kənarlarının sayını göstərir. İkinci sətir s və f təbii ədədlərini (1 ≤ s, f ≤ n, s ≠ f) - aralarındakı yolun uzunluğunu tapmaq istədiyiniz zirvələrin nömrələrini göstərir. Sonrakı m sətirin hər biri üç ədəd b[i], e[i] və w[i] - i-ci kənarın uclarının nömrələri və onun çəkisini göstərir (1 ≤ b[i], e[i] ≤ n, 0 ≤ w[i] ≤ 100000).

Çıxış şərtləri

Birinci sətirdə zirvələr s və f arasında minimal yolun uzunluğunu göstərin. İkinci sətirdə boşluqla ayrılmış şəkildə s-dən f-ə ən qısa yoldakı zirvələri ardıcıllıqla göstərin. Əgər s-dən f-ə yol mövcud deyilsə, -1 göstərin.

Nümunələr