E. Классическая задача
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
768 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан взвешенный неориентированный граф из n вершин и m ребер. Найдите кратчайший путь из вершины s в вершину t, либо определите, что пути не существует.

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

В первой строке записано два целых числа, разделенных пробелом, n и m (1 ≤ n ≤ 105; 0 ≤ m ≤ 105).

В следующих m строках приведено описание ребер графа. В i-й строке записано три целых числа, разделенных пробелами — ui, vi, xi (1 ≤ ui, vi ≤ n; 0 ≤ xi ≤ 105). Это означает, что вершины с номерами ui и vi соединены ребром длины 2xi (2 в степени xi).

В последней строке записаны два целых числа, разделенных пробелом — номера вершин s и t.

Вершины пронумерованы от 1 до n. В графе отсутствуют кратные ребра и петли.

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

В первой строке выведите остаток от деления длины кратчайшего пути на 1000000007 (109 + 7), если путь существует, и -1, если пути не существует.

В случае, если путь существует, во второй строке выведите целое число k —количество вершин в кратчайшем пути из вершины s в вершину t; в третьей строке выведите k чисел, разделенных пробелами — вершины кратчайшего пути в порядке посещения. Первая вершина должна быть вершиной s, последняя — вершиной t. Если существует несколько кратчайших путей, выведите любой.

Примеры
Входные данные
4 4
1 4 2
1 2 0
2 3 0
3 4 0
1 4
Выходные данные
3
4
1 2 3 4
Входные данные
4 3
1 2 4
2 3 5
3 4 6
1 4
Выходные данные
112
4
1 2 3 4
Входные данные
4 2
1 2 0
3 4 1
1 4
Выходные данные
-1
Примечание

Путем из вершины s в вершину t называется последовательность вершин v0, ..., vk, такая что v0 = s, vk = t, и для любого i от 0 до k - 1 вершины vi и vi + 1 соединены ребром.

Длиной пути называется сумма длин ребер между vi и vi + 1 для всех i от 0 до k - 1.

Кратчайшим путем из s в t называется путь, длина которого минимальна среди всех возможных путей из s в t.