그래프 7: 최단 경로

시간 제한: 1000 ms메모리 제한: 256 MBSilver III4작성자: 관리자

점 (N)개와 방향 간선 (M)개짜리 가중치 그래프가 있다. 시작점 (s)에서 각 점까지의 최단 거리를 구하라. 갈 수 없으면 (-1)로 표시한다. 간선의 비용은 모두 0 이상이다.

입력

첫 줄에 (N), (M). 다음 (M)줄에 (u), (v), (w)((u)에서 (v)로 비용 (w)). 마지막 줄에 (s) ((1 \le N \le 1000), (0 \le w \le 10^4)).

출력

1번부터 (N)번까지 최단 거리를 공백으로 구분해 출력(못 가면 (-1)).

입력

문제 통계

1

전체 제출

1

정답

100%

정답률

1

정답자 수

출력

0 2 3 4 6