최단 경로 아니면 음수 사이클

$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$ 로 가는 경로가 존재한다.