32514번 - 최단 경로 아니면 음수 사이클 스페셜 저지

문제

$N$ 개의 정점과 $M$ 개의 간선을 가진 그래프가 주어진다. 그래프의 정점은 0,ドル 1, \ldots, N-1$ 으로 번호가 매겨져 있다. 또한, 정점 $s$ 가 주어진다. 모든 정점 0ドル \le i \le N - 1$ 에 대해 $s$ 에서 $i$ 로 가는 경로가 존재한다.모든 정점 0ドル \le i \le N - 1$ 에 대해 $s$ 에서 $i$ 로 가는 경로가 존재한다.

$i$ 번 간선은 $a_i$ 번 정점에서 $b_i$ 번 정점으로 가며, 정수 $c_i$ 의 가중치를 가진다. $c_i$ 는 음수일 수 있다.

만약에 그래프에 음수 사이클이 있으면, 이 중 아무거나 반환하라.

음수 사이클이 없다면, 모든 정점 0ドル \le t \le N - 1$ 에 대해서, $s$ 에서 $t$ 로 가는 최단 경로의 길이를 출력하라.

입력

첫 번째 줄에 정수 $N, M, s$ 가 주어진다.

이후 $M$ 개의 줄에 $a_i, b_i, c_i$ 가 주어진다.

출력

그래프에 음수 사이클이 존재한다면:

• 첫 번째 줄에 CYCLE을 출력하라.
• 두 번째 줄에 $k$ 를 출력하라. 이는 음수 사이클의 간선 수를 의미한다. $k \geq 1$ 이어야 한다.
• 세 번째 줄에 $k+1$ 개의 정수 $u_0, u_1, \ldots, u_k$ 를 출력하라. $u_i$ 와 $u_{i+1}$ 은 사이클의 $i$ 번째 간선의 시작 정점과 끝 정점이어야 한다. $u_0 = u_k$ 여야 하며, 이 사이클은 각 간선을 최대 한번만 포함해야 한다.

그래프에 음수 사이클이 존재하지 않는다면:

• 첫 번째 줄에 PATH를 출력한다.
• 두 번째 줄에 $N$ 개의 정수 $dist_0, dist_1, \ldots, dist_{N-1}$ 을 출력하라. $dist_i$ 는 $s$ 에서 $i$ 로 가는 최단 경로의 가중치 합을 뜻한다.

제한

• 2ドル \le N \le 20,000円$
• 1ドル \le M \le 20,000円$
• 0ドル \le s < N$
• 0ドル \le a_i, b_i \le N$
• $(a_i, b_i) \neq (a_j, b_j)$ ($i \neq j$)
• $-10^4 \le c_i \le 10^4$
• 모든 정점 0ドル \le i \le N - 1$ 에 대해 $s$ 에서 $i$ 로 가는 경로가 존재한다.

힌트