Background

양의 가중치를 가진 방향 그래프에서 시작 정점으로부터의 거리를 계산한다.

Description

정점이 $1$번부터 $V$번까지 번호가 매겨진 방향 그래프가 주어진다.
시작 정점 $S$에서 각 정점까지의 최단 거리를 구하여라.

간선의 가중치는 모두 $1$ 이상 $10$ 이하의 정수이다.
같은 두 정점 사이에 여러 개의 방향 간선이 존재할 수 있다.

Format

Input

첫째 줄에 두 정수 $V$와 $E$가 공백으로 구분되어 주어진다.

둘째 줄에 시작 정점 $S$가 주어진다.

다음 $E$개의 줄에는 세 정수 $u$, $v$, $w$가 공백으로 구분되어 주어진다.
이는 $u$번 정점에서 $v$번 정점으로 가는 가중치 $w$의 방향 간선이 있음을 의미한다.

입력은 다음 조건을 만족한다.

$1 \leq V \leq 20000$

$0 \leq E \leq 120000$

$1 \leq S \leq V$

$1 \leq u, v \leq V$

$u \neq v$

$1 \leq w \leq 10$

Output

$1$번 정점부터 $V$번 정점까지 순서대로, 시작 정점 $S$에서 해당 정점까지의 최단 거리를 한 줄에 하나씩 출력한다.

도달할 수 없는 정점에 대해서는 INF를 출력한다.

Samples

6 8
3
3 1 4
3 2 1
2 1 2
1 4 7
2 4 5
4 5 1
5 2 1
6 5 3

3
1
0
6
7
INF

4 4
4
4 1 10
4 2 3
2 1 4
1 3 2

7
3
9
0

Limitation

3s, 256MiB for each test case.