Расстояние между вершинами

Input

В первой строке заданы два положительных целых числа $n$ и $m$ $(1 \leq n \leq 1 0^{5}, 1 \leq m \leq 2 \cdot 1 0^{5})$ (1 \le n \le 10^5,\ 1 \le m \le 2 \cdot 10^5) — количество вершин и рёбер в графе. Во второй строке заданы два положительных целых числа $s$ и $t$ $(1 \leq s, t \leq n, s \neq = t)$ (1 \le s, t \le n,\ s \ne t) — номера вершин, между которыми необходимо найти кратчайший путь.

Далее в следующих $m$ строках содержатся описания рёбер. Каждое ребро $i$ задаётся тремя целыми числами $b_{i}$ b_i, $e_{i}$ e_i и $w_{i}$ w_i $(1 \leq b_{i}, e_{i} \leq n, 0 \leq w_{i} \leq 100)$ (1 \le b_i, e_i \le n,\ 0 \le w_i \le 100) — номерами соединяемых вершин и весом ребра.

Output

Выведите вес кратчайшего пути между вершинами $s$ и $t$ , либо $- 1$ , если такого пути не существует.

Examples

Example 1

Loading