题目描述

给定一个有向图，你的任务是判断图中是否存在负权环，并给出该环的一个实例。

负权环指的是一个有向环，环上所有边的权值之和小于 $0$。

输入格式

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

接下来 $m$ 行描述各条边，每行包含三个整数 $a,b,c$：表示存在一条从节点 $a$ 到节点 $b$ 的有向边，其权值为 $c$。

输出格式

如果图中存在负权环，首先输出 YES，然后按顺序输出环上的节点。若有多个负权环，输出任意一个即可。

如果不存在负权环，则输出 NO。

数据范围

• $1 \le n \le 2500$
• $1 \le m \le 5000$
• $1 \le a,b \le n$
• $-10^9 \le c \le 10^9$

来源

CSES 1197 Cycle Finding。

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

YES
1 2 4 1