Вам заданий опис мережі доріг країни. Ваша задача - знайти довжину найкоротшого шляху між містами \(S\) та \(F\).

Формат вхідних даних

Перший рядок містить числа \(N\) та \(M\) (\(1 \le N \le 100000\), \(0 \le M \le 300000\)), де \(N\) - кількість міст\(, а M\) – кількість доріг.

Кожен з \(M\) наступних рядків містить опис двосторонньої дороги – три цілих числа \(V1\), \(V2\) та \(W\) (\(1 \le V1,V2 \le N\), \(1 \le W \le 10^6\)).
Це означає, що існує дорога довжини \(W\), між містами \(V1\) та \(V2\).

В останньому рядку знаходяться два числа \(S\) та \(F\) – номера міст, між якими необхідно порахувати найкоротшу відстань (\(1 \le S,F \le N\))

Формат вихідних даних

Виведіть єдине чило - відстань між потрібними містами. Якщо між відповідними містами шдяху не існує - виведіть -1.

Приклад вхідних даних

6 4
1 2 7
2 4 8
4 5 1
4 3 100
3 1

Приклад вихідних даних

115