最短路

【题目描述】

给定一张由 $N$ 个顶点和 $M$ 条边构成的简单有向带权图。 第 $i$ 条边从顶点 $a_i$ 指向顶点 $b_i$，权值为 $c_i$。 请求出从顶点 $s$ 到顶点 $t$ 的（简单）最短路，或者报告不存在这样的路径。 若存在多条最短路，输出其中任意一条即可。

【输入】

$N$ $M$ $s$ $t$
$a_0$ $b_0$ $c_0$
$a_1$ $b_1$ $c_1$
$a_2$ $b_2$ $c_2$
$\vdots$
$a_{M - 1}$ $b_{M - 1}$ $c_{M - 1}$

【输出】

若不存在从顶点 $s$ 到顶点 $t$ 的路径，输出 -1。 否则，按以下格式输出其中一条最短路。

$X$ $Y$
$u_0$ $v_0$
$u_1$ $v_1$
$u_2$ $v_2$
$u_{Y - 1}$ $v_{Y - 1}$

$X$ 表示最短路的长度。 $Y$ 表示该路径包含的边数。 $u_i$ 与 $v_i$ 分别表示路径中第 $i$ 条边的起点与终点。

【输入样例】

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】

2 1 0 1
1 0 10

【输出样例2】

-1

【数据范围】

• $2 \leq N \leq 500000$
• $1 \leq M \leq 500000$
• $0 \leq s \lt N$
• $0 \leq t \lt N$
• $s \neq t$
• $0 \leq a_i \lt N$
• $0 \leq b_i \lt N$
• $a_i \neq b_i$
• $(a_i, b_i) \neq (a_j, b_j) (i \neq j)$
• $0 \leq c_i \leq 1000000000$

【来源】

Library Checker（yosupo06） shortest_path

本题为 special judge（输出任意合法解），暂不可本地评测。