Təpələr arasındakı məsafə

Çəkili qraf verilib. İki təpə arasındakı minimal yolun çəkisini tapmalı.

Giriş verilənləri

İlk sətirdə qrafın uyğun olaraq təpələrinin və tillərinin sayını ifadə edən iki natural n və m (n ≤ 1000, m ≤ 10000) ədədləri verilir. İkinci sətirdə aralarındakı məsafənin tapılması tələb olunan təpələrin nömrəsini ifadə edən iki natural s və t (s, t ≤ n, s ≠ t) ədədələri verilir. Növbəti m sətrin hər biri tili ifadə edir. i nömrəli sətir uyğun olaraq tilin birləşdirdiyi təpə nöqtələri və çəkisini ifadə edən üç natural ədəd ilə: b[i], e[i] və w[i] (b[i], e[i] ≤ n, 0 ≤ w[i] ≤ 10^5) ifadə olunub. s-dən t-yə yolun olduğuna zəmanət verilir.

Çıxış verilənləri

Yeganə sətirdə s və t təpələri arasındakı minimal yolun çəkisini ifadə edən natural ədədi verməli.

Nümunələr