Çə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ə: bi, ei və wi (bi, ei ≤ n, 0 ≤ wi ≤ 105) 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.