You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-1197 题。

题目描述

给定一个有向图，要求判断该图是否包含负权环，并且给出一个负权环的示例。

输入格式

第一行包含两个整数 $n$ 和 $m$：分别表示图中的节点数和边数。节点编号为 $1,2,…,n$。

接下来的 $m$ 行，每行描述一个边，包含三个整数 $a$, $b$ 和 $c$：表示从节点 $a$ 到节点 $b$ 的一条边，边的权重为 $c$。

输出格式

如果图中包含负权环，首先输出 YES，然后输出环中的节点，按顺序排列。如果有多个负权环，可以输出其中任何一个。

如果图中没有负权环，输出 NO。

样例

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

YES
1 2 4 1

说明/提示

$1 \leq n \leq 2500$；

$1 \leq m \leq 5000$；

$1 \leq a,b \leq n$；

$-10^9 \le c \le 10^9$。