Positive Cycle Detection

You are given a directed weighted graph with N vertices and M edges. Each edge is represented by a triple (u, v, w) indicating a directed edge from vertex u to vertex v with weight w. Your task is to determine whether the graph contains a positive cycle (i.e. a cycle whose total weight sum is greater than 0).

The algorithm can be implemented by using a variant of the Bellman-Ford algorithm. In this version, the update condition checks if distance[u] + w > distance[v] for an edge (u, v, w). If this condition can be satisfied in the N-th iteration, then a positive cycle exists.

The relation can be expressed mathematically as:

\[ distance[v] < distance[u] + w \]

If after N relaxations an update still occurs, output "Yes" indicating that there is a positive cycle, otherwise output "No".

inputFormat

The first line contains two integers N and M where N is the number of vertices and M is the number of edges. The following M lines each contain three integers u, v, and w representing a directed edge from vertex u to vertex v with weight w.

You should read input from standard input (stdin).

outputFormat

Output a single line to standard output (stdout): print "Yes" if the graph contains a positive cycle, otherwise print "No".

3 3
1 2 2
2 3 3
3 1 1

Yes