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

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

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

В первой строке записано два целых числа, разделенных пробелом, $$$n$$$ и $$$m$$$ ($$$1 \leq n \leq 10^5$$$; $$$0 \leq m \leq 10^5$$$).

В следующих $$$m$$$ строках приведено описание ребер графа. В $$$i$$$-й строке записано три целых числа, разделенных пробелами — $$$u_i$$$, $$$v_i$$$, $$$x_i$$$ ($$$1 \leq u_i, v_i \leq n$$$; $$$0 \leq x_i \leq 10^5$$$). Это означает, что вершины с номерами $$$u_i$$$ и $$$v_i$$$ соединены ребром длины $$$2^{x_i}$$$ (2 в степени $$$x_i$$$).

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

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

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

В первой строке выведите остаток от деления длины кратчайшего пути на $$$1000\,000\,007$$$ ($$$10^9 + 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$$$ называется последовательность вершин $$$v_0$$$, ..., $$$v_k$$$, такая что $$$v_0 = s$$$, $$$v_k = t$$$, и для любого $$$i$$$ от 0 до $$$k - 1$$$ вершины $$$v_i$$$ и $$$v_{i+1}$$$ соединены ребром.

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

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