Дан неориентированный взвешенный граф. Найти вес минимального пути между двумя вершинами.

Входные данные

Первая строка содержит натуральные числа n, m, s и f (n ≤ 5000, m ≤ 105, 1 ≤ s, f ≤ n, s ≠ f) - количество вершин и ребер графа а также номера вершин, длину пути между которыми требуется найти.

Следующие m строк содержат по три натуральных числа bi, ei и wi - номера концов i-ого ребра и его вес соответственно (1 ≤ bi, ei ≤ n, 0 ≤ wi ≤ 105).

Выходные данные

Первая строка должна содержать вес минимального пути между вершинами s и f. Во второй строке через пробел выведите вершины на кратчайшем пути из s в f в порядке обхода. Если путь из s в f не существует, выведите -1.