You are given 2 integers N and M , N is the number of vertices, M is the number of edges. You'll also be given ai, bi and wi where ai and bi represents an edge from a vertex ai to a vertex bi and wi respresents the weight of that edge. Task is to find if it contains a negative weight cycle or not.
Input Format
First line contains two space separated integers,N and M. Then M lines follow, each line has 3 space separated integers ai, bi and wi.
Output Format
Print 1 if it contains a negative weight cycle else print 0.
Constraints
1<= N <= 10^4 1<= M <= 10^6 0<= ai, bi <= N-1 1<= wi <= 1000
Example
Input
3 3 0 1 -1 1 2 -4 2 0 3
Output
1