题目描述

给定$n$个点$m$条边的有向图，请求出图中是否存在从$1$号点出发能到达的负环。如果存在，输出YES；否则，如果从$1$号点无法到达$n$号点，输出NO；否则，输出从$1$号点到$n$号点的最短路长度。

负环的定义：一条边权之和为负数的回路。

输入格式

第一行输入两个整数$n,m$。 接下来$m$行，每行输入三个整数$u,v,w$，表示一条$u\rightarrow v$，权值为$w$的有向边。

输出格式

输出一行，表示你的答案。

样例输入 #1

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

样例输出 #1

YES

说明/提示

有$1\leq n\leq 10^3,1\leq m\leq 5\times 10^3,-10^4\leq w\leq 10^4$。