You are given a weighted undirected graph on $$$n$$$ vertices and $$$m$$$ edges. Find the shortest path from vertex $$$s$$$ to vertex $$$t$$$ or else state that such path doesn't exist.

Input

The first line of the input contains two space-separated integers — $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^5$$$; $$$0 \leq m \leq 10^5$$$).

Next $$$m$$$ lines contain the description of the graph edges. The $$$i$$$-th line contains three space-separated integers — $$$u_i$$$, $$$v_i$$$, $$$x_i$$$ ($$$1 \leq u_i, v_i \leq n$$$; $$$0 \leq x_i \leq 10^5$$$). That means that vertices with numbers $$$u_i$$$ and $$$v_i$$$ are connected by edge of length $$$2^{x_i}$$$ (2 to the power of $$$x_i$$$).

The last line contains two space-separated integers — the numbers of vertices $$$s$$$ and $$$t$$$.

The vertices are numbered from $$$1$$$ to $$$n$$$. The graph contains no multiple edges and self-loops.

Output

In the first line, print the remainder after dividing the length of the shortest path by $$$1000\,000\,007$$$ ($$$10^9 + 7$$$) if the path exists, and $$$-1$$$ if the path doesn't exist.

If the path exists, print in the second line integer $$$k$$$ — the number of vertices in the shortest path from vertex $$$s$$$ to vertex $$$t$$$; in the third line print $$$k$$$ space-separated integers — the vertices of the shortest path in the visiting order. The first vertex should be vertex $$$s$$$, the last vertex should be vertex $$$t$$$. If there are multiple shortest paths, print any of them.

Note

A path from vertex $$$s$$$ to vertex $$$t$$$ is a sequence $$$v_0$$$, ..., $$$v_k$$$, such that $$$v_0 = s$$$, $$$v_k = t$$$, and for any $$$i$$$ from 0 to $$$k - 1$$$ vertices $$$v_i$$$ and $$$v_{i+1}$$$ are connected by an edge.

The length of the path is the sum of weights of edges between $$$v_i$$$ and $$$v_{i+1}$$$ for all $$$i$$$ from 0 to $$$k - 1$$$.

The shortest path from $$$s$$$ to $$$t$$$ is the path which length is minimum among all possible paths from $$$s$$$ to $$$t$$$.

The Classic Problem

Examples