#321 최단 경로

문제

Statement language

정점이 $1$ 번부터 $N$ 번까지 번호가 붙은 방향 가중 그래프와 시작점 $S$ 가 주어진다. $S$ 에서 모든 정점까지의 최단 거리를 출력하여라. 간선 가중치는 음이 아닌 정수이며, 중복 간선과 자기 간선이 허용된다.

입력은 다음과 같은 형식으로 주어진다.

$N\ M\ S$ $u_1\ v_1\ w_1$

첫째 줄에 $N$ 개의 값을 출력한다. 도달할 수 없는 정점의 거리는 INF로 출력한다.

#	Score	Constraints
1	20	$N \leq 200$ , $M \leq 500$
2	80	추가적인 제약조건이 없다.

Input

Output

0 1010 1000 1110 1111 INF