题目描述

最近牢超有点迷，像是喝醉了一样。

有一天，牢超出去觅食，路上走着走着就不小心走错到了女寝门口，刚好你也在，就直接上去拦住了牢超，为了帮助牢超安全走到曹氏鸭脖，并不再走错，你决定帮他看一下地图。

由于牢超喜欢看学校的美女，他想把地图上所有地方都走一遍，但是当牢超走到边权和小于零的环，他会一直无尽的循环走下去直到饿死。给定一个有向图,其中 $n$ 个点，$m$ 条边，你只需要告诉他地图上是否有边权和为负数的环。

这里定义边权和小于零的都是负环

输入格式

第一行两个正整数 $n,m$（$1 \le n,m \le 1\times 10^5$)

第二行到第 $m+1$ 行，每行三个整数 $u,v$ 和 $c$，表示一条 $u$ 到 $v$ 的有向边，边权为 $c$（$-10^9 \le c \le 10^9$)

输出格式

如果存在负环，输出 $1$，否则输出 $0$。

输入样例

 3 3
 1 2 -9
 2 3 1
 3 1 1

输出样例

1

提示

有一个负环：$1\overset{-9}{\to} 2\overset{1}{\to}3\overset{1}{\to}1$ 这个环的边权和为 $-7$。