# Shortest Path

AC一覧

## Problem Statement問題文

You are given a simple directed weighted graph, consisting of $N$ vertices and $M$ edges.
The $i$-th edge is directed from vertex $a_i$ to vertex $b_i$ and has a weight of $c_i$.
Find the (simple) shortest path from vertex $s$ to vertex $t$, or report that no such path exists.
If there are multiple shortest paths, print any of them.

$N$ 頂点 $M$ 辺の単純重み付き有向グラフが与えられます。$i$番目の辺は頂点 $a_i$ から頂点 $b_i$ に張られており、重さは $c_i$ です。

## Constraints制約

• $2 \leq N \leq 500{,}000$
• $1 \leq M \leq 500{,}000$
• $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 10^{9}$

## Input入力

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


## Output出力

If there are no paths from vertex $s$ to vertex $t$, output -1. Otherwise, output one of the shortest paths in the following format.

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


$X$ represents length of the shortest path. $Y$ represents the number of edges in the path. $u_i$ and $v_i$ are beginning and end of the $i$-th edge in the path, respectively.

$X$は最短距離、$Y$は出力するパスの辺数を表し、$u_i, v_i$はそれぞれ$i$番目に通る辺の始点と終点を表します。 同じ頂点を $2$ 回以上通ってはなりません。

## Sampleサンプル

### # 1

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

-1


Timelimit: 5 secs

Before submitting, please confirm terms and conditions