最短路径（Shortest Path）

问题描述

给你一个含 $N$ 个顶点、$M$ 条边的简单有向带权图。第 $i$ 条边从顶点 $a_i$ 指向顶点 $b_i$，权重为 $c_i$。
请找出从顶点 $s$ 到顶点 $t$ 的一条最短路径（按边权和最小）；若不存在路径，输出 -1。

若有多个最短路径，输出任意一条即可。

约束条件

• $2 \leq N \leq 5 \times 10^5$
• $1 \leq M \leq 5 \times 10^5$
• $0 \leq s, t < N$
• $s \ne t$
• $0 \leq a_i, b_i < N$
• $a_i \ne b_i$
• $(a_i, b_i) \ne (a_j, b_j)$ 当 $i \ne j$
• $0 \leq c_i \leq 10^9$

输入格式

$N\ M\ s\ t$
$a_0\ b_0\ c_0$
$a_1\ b_1\ c_1$
:
$a_{M-1}\ b_{M-1}\ c_{M-1}$

输出格式

• 若无路径：

  -1

• 否则：

  $X\ Y$
  $u_0\ u_1\ \dots\ u_{Y-1}$

其中：

• $X$ 是最短路径的总权重；
• $Y$ 是路径上的边数；
• $u_i$ 是第 $i$ 条边的起点顶点（即路径顶点序列为 $u_0, u_1, \dots, u_Y$，其中 $u_Y = t$）。

5 7 2 3
0 3 5
0 4 3
2 4 2
4 3 10
4 0 7
2 1 5
1 0 1

11 3
2 1
1 0
0 3

2 1 0 1
1 0 10

-1