İstiqamətlənməmiş çəkili qraf verilir. İki təpə arasındakı minimal yolun çəkisini tapmalı.

Giriş verilənləri

Giriş faylının ilk sətri n, m, s və f (n ≤ 5000, m ≤ 100000, 1 ≤ s, f ≤ n, s ≠ f) natural ədədlərini ehtiva edir, uyğun olaraq - təpələrin sayı, tillərin sayı, aralarındakı məsafənin tapılması tələb olunan təpələrin nömrələri.

Növbəti m sətir bi, ei və wi natural ədədlərini ehtiva edir, uyğun olaraq - i-ci tilin uclarının nömrəsi və onun çəkisi (1 ≤ bi, ei ≤ n, 0 ≤ wi ≤ 100000).

Çıxış verilənləri

İlk sətirdə bir natural ədəd veilməli - s və f təpələri arasındakı minimal yolun çəkisi. İkinci sətirdə isə boşluqla ayrılmış s-dən f-ə gedən ən qısa yoldakı təpələri keçilmə ardicilliğı ilə verməli. Əgər s-dən f-ə yol yoxdursa -1 verməli.