単一始点最短経路

与えられたグラフ $G = (V, E)$ と始点 $r$ について、単一始点最短経路の重みを求めるプログラムを作成してください。$G$ のノード $r$ を始点とし、$r$ から各ノードについて、最短経路上の辺の重みの総和を出力してください。

入力

$|V| \; |E| \; r$
$s_0 \; t_0 \; d_0$
$s_1 \; t_1 \; d_1$
:
$s_{|E|−1} \; t_{|E|−1} \; d_{|E|−1}$

$|V|$, $|E|$ はそれぞれグラフ $G$の頂点の数と辺の数を示す。グラフ $G$の頂点にはそれぞれ $0, 1, ..., |V|-1$ の番号が付けられている。$r$ は始点の番号である。

$s_i$, $t_i$ はグラフ $G$ の $i$ 番目の辺が結ぶ２つの頂点を表す（有向）。$d_i$ は $i$ 番目の辺の重みである。

出力

出力は $|V|$ 行からなる。各頂点 $0, 1, ..., |V|-1$ について、始点 $r$ からの最短経路上の重みの総和を順番に出力する。ただし、$r$ からの経路が存在しない場合は INF と出力する。

制約

• $1 \leq |V| \leq 100000$
• $0 \leq d_i \leq 10000$
• $ 0 \leq |E| \leq 500000$
• $G$ に平行辺はない
• $G$ に自己ループはない

入力例 1

4 5 0
0 1 1
0 2 4
1 2 2
2 3 1
1 3 5

出力例 1

0
1
3
4

入力例 2

4 6 1
0 1 1
0 2 4
2 0 1
1 2 2
3 1 1
3 2 5

出力例 2

3
0
2
INF

---