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

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

Первая строка содержит натуральные числа n и m (n ≤ 2000, m ≤ 50000) - количество вершин и рёбер графа. Вторая строка содержит натуральные числа s и f (1 ≤ s, f ≤ n, s ≠ f) - номера вершин, длину пути между которыми требуется найти. Следующие m строк содержат по три числа bi, ei и wi - номера концов i-ого ребра и его вес соответственно (1 ≤ bi, ei ≤ n, 0 ≤ wi ≤ 100000).

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

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