Відстань між вершинами

Дано зважений граф. Потрібно визначити вагу найкоротшого шляху між двома заданими вершинами.

Вхідні дані

Перший рядок містить два натуральних числа n і m (n ≤ 1000, m ≤ 10000) — кількість вершин і ребер графа відповідно. Другий рядок містить натуральні числа s і t (s, t ≤ n, s ≠ t) — номери вершин, між якими потрібно знайти шлях. Наступні m рядків описують ребра графа. Кожне ребро номер i задається трьома натуральними числами b[i], e[i] і w[i] — номери кінцевих вершин ребра та його вага відповідно (b[i], e[i] ≤ n, 0 ≤ w[i] ≤ 10^5). Гарантується, що існує шлях з s до t.

Вихідні дані

Виведіть одне натуральне число — вагу найкоротшого шляху між вершинами s і t.

Приклади