CF464E The Classic Problem

给定一个有 $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}}$ 的无向边。 最后一行包含两个用空格分隔的整数，表示起点和终点的编号 $s$ 和 $t$。 顶点编号为 $1$ 到 $n$。图中无重边无自环。

如果从 $s$ 到 $t$ 存在路径，第一行输出最短路径长度对 $1000000007$（$10^{9}+7$）取余的结果；否则输出 $-1$。 如果存在路径，第二行输出路径上的点数 $k$；第三行输出 $k$ 个用空格分隔的顶点编号，按访问顺序给出，第一个必须是 $s$，最后一个必须是 $t$。如果存在多条最短路径，输出任意一条均可。

从顶点 $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$ 的最短路径是所有可能路径中长度最短的那一条路径。 由 ChatGPT 5 翻译