Shortest Path or Negative Cycle

A graph with $N$ vertices and $M$ edges is given. The vertices are numbered $0, 1, \ldots, N-1$. A vertex $s$ is also given. For every vertex $0 \le i \le N-1$, there is a path from $s$ to $i$.

Edge $i$ goes from vertex $a_i$ to vertex $b_i$ and has weight $c_i$. $c_i$ may be negative.

If the graph has a negative cycle, return any one of them.

If the graph has no negative cycle, print the length of the shortest path from $s$ to $t$ for every vertex $0 \le t \le N-1$.

The first line contains the integers $N$, $M$, and $s$.

Each of the next $M$ lines contains $a_i$, $b_i$, and $c_i$.

If the graph has a negative cycle:

• The first line prints CYCLE.
• The second line prints $k$, the number of edges in the negative cycle. $k \ge 1$.
• The third line prints $k+1$ integers $u_0, u_1, \ldots, u_k$. $u_i$ and $u_{i+1}$ are the start and end vertices of the $i$-th edge of the cycle. $u_0 = u_k$, and the cycle includes each edge at most once.

If the graph has no negative cycle:

• The first line prints PATH.
• The second line prints $N$ integers $dist_0, dist_1, \ldots, dist_{N-1}$, where $dist_i$ is the sum of weights on the shortest path from $s$ to $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$
• For every vertex $0 \le i \le N-1$, there is a path from $s$ to $i$.