CF464E.The Classic Problem

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.

给你一个包含 $n$ 个顶点和 $m$ 条边的带权无向图。求从顶点 $s$ 到顶点 $t$ 的最短路径；若不存在这样的路径，则说明其不存在。

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.

输入的第一行包含两个用空格分隔的整数——$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$。图中不含重边和自环。

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.

第一行输出最短路径长度对 $1000\,000\,007$（即 $10^9 + 7$）取模的余数；若最短路径不存在，则输出 $-1$。

若最短路径存在，则第二行输出整数 $k$ —— 从顶点 $s$ 到顶点 $t$ 的最短路径所经过的顶点个数；第三行输出 $k$ 个用空格分隔的整数 —— 按访问顺序给出该最短路径上的各顶点。其中第一个顶点应为 $s$，最后一个顶点应为 $t$。若存在多条最短路径，输出任意一条即可。

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$.

从顶点 $s$ 到顶点 $t$ 的一条路径是一个序列 $v_0$, ..., $v_k$，满足 $v_0 = s$、$v_k = t$，且对任意 $i$（$0 \le i \le k - 1$），顶点 $v_i$ 与 $v_{i+1}$ 由一条边相连。

该路径的长度定义为：对所有 $i$（$0 \le i \le k - 1$），边 $(v_i, v_{i+1})$ 的权重之和。

从 $s$ 到 $t$ 的最短路径是指：在所有从 $s$ 到 $t$ 的可能路径中，长度最小的那条路径。