최단 경로

$N$개의 정점과 $M$개의 간선으로 이루어진 단순 방향 가중 그래프가 주어진다.
$i$번째 간선은 정점 $a_i$에서 정점 $b_i$로 향하며, 가중치는 $c_i$이다.
정점 $s$에서 정점 $t$까지의 (단순) 최단 경로를 구하거나, 그러한 경로가 존재하지 않음을 보고한다.
최단 경로가 여러 개라면 그중 아무거나 출력한다.

제약 조건

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

$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$번째 간선의 시작점과 끝점을 나타낸다.