10063 벨만-포드 Gold IV

문제

N개의 정점과 M개의 간선을 가진 방향 그래프에서, 시작 정점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 간선의 가중치는 음수일 수 있다.

음수 사이클이 존재하면 -1을 출력한다.

입력

첫째 줄에 정점의 수 N (1 ≤ N ≤ 500), 간선의 수 M (1 ≤ M ≤ 6,000), 시작 정점 S가 주어진다. 다음 M개의 줄에 u, v, w가 주어진다. (-10,000 ≤ w ≤ 10,000)

출력

음수 사이클이 있으면 첫째 줄에 -1을 출력한다. 없으면 각 정점까지의 최단 거리를 한 줄에 하나씩 출력한다. 도달할 수 없으면 INF를 출력한다.

3 4 1
1 2 4
1 3 3
2 3 -4
3 1 -2

0
4
3