Detecting Reachable Negative Cycle

Given a directed graph with \(n\) vertices and \(m\) edges, determine whether there exists a negative cycle that is reachable from vertex \(1\).

A negative cycle is defined as a cycle (a path that starts and ends at the same vertex) for which the sum of the edge weights is negative, i.e.,

\[ \sum_{i=1}^{k} w_i < 0 \]

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of vertices and edges respectively. Each of the following \(m\) lines contains three integers \(u\), \(v\) and \(w\), representing a directed edge from vertex \(u\) to vertex \(v\) with weight \(w\).

outputFormat

Print "YES" if there exists a negative cycle that is reachable from vertex \(1\); otherwise, print "NO".

sample

3 3
1 2 4
2 3 5
3 1 6

NO