Detecting Negative Weight Cycle in a Weighted Directed Graph

You are given a weighted directed graph with n vertices and m edges. Each edge is described by three integers u, v and w indicating a directed edge from vertex u to vertex v with weight w.

Your task is to determine whether the graph contains a negative weight cycle. A negative weight cycle is a cycle whose sum of edge weights is negative. In other words, if there exists a cycle in the graph such that $$ \sum_{(u,v,w)\in cycle} w < 0, $$ then output YES, otherwise output NO.

You are encouraged to implement an efficient solution using the Bellman-Ford algorithm. In this algorithm, the following relaxation condition is repeatedly applied: $$ \text{if } \; \text{distance}[v] > \text{distance}[u] + w \; \text{ then update } \; \text{distance}[v] = \text{distance}[u] + w. $$

inputFormat

The input is given from stdin in the following format:

 n m
 u1 v1 w1
 u2 v2 w2
 ...
 um vm wm

where:

• n is the number of vertices.
• m is the number of edges.
• Each of the next m lines contains three integers u, v and w representing a directed edge from vertex u to vertex v with weight w.

outputFormat

Output a single line to stdout containing YES if the graph contains at least one negative weight cycle, or NO otherwise.

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

YES