Коль Дейкстрý писать без кучи,

То тайм-лимит ты получишь...

А в совсем другой задаче

Юзай кучу Фибоначчи!

___________________________________________

Спектакль преподавателей ЛКШ.июль-2007

İstiqamətlənməmiş çəkili qraf verilir.

İki təpə arasındakı ən qısa yolun çəkisini tapmaq tələb olunur.

Giriş verilənləri

Giriş faylının ilk sətri təpələrin və tillərin sayını ifadə edən iki natural n və m (1 ≤ n ≤ 105, 1 ≤ m ≤ 2 * 105) ədədlərini ehtiva edir. Giriş vaylının ikinci sətri aralarındakı uzunluğunu tapmaq tələb olunan təpələrin nömrələrini ifadə edən s və t (1 ≤ s, t ≤ n, s ≠ t) natural ədədlərini ehtiva edir.

Növbəti m sətrin hər biri tillərin təsvirini ehtiva edir. i nömrəli til tilin sonluqlarının nömrələrini və onun çəkisini ifadə edən üç tam bi, ei və wi (1 ≤ bi, ei ≤ n, 0 ≤ wi ≤ 100) ədədləri ilə ifadə olunur.

Çıxış verilənləri

Çıxış faylının yeganə sətri s və t təpələri arasındakı ən kiçik yolun çəkisini ifadə edən yeganə tam ədədı və ya belə yol mövcud deyilsə -1 ehtiva etməlidir.