Positive Weight Cycle Detection

In this problem, you are given a directed graph with ( n ) nodes and ( m ) edges. Each edge has an associated integer weight. Your task is to determine whether there exists a cycle (i.e., a sequence of vertices ( v_1, v_2, \dots, v_k, v_1 )) such that the sum of its weights is positive. Specifically, if the cycle has weights ( w_1, w_2, \dots, w_k ), then you need to check if [ w_1 + w_2 + \cdots + w_k > 0 ]

If such a cycle exists anywhere in the graph (the graph might be disconnected), output "YES"; otherwise, output "NO".

Note: Vertices are numbered from 1 to ( n ). It is possible that the graph has multiple components. A multi-source variant of the Bellman-Ford algorithm (or SPFA) can be used to solve this problem.

inputFormat

The first line contains two integers ( n ) and ( m ) (( 1 \leq n \leq 10^5 ), ( 0 \leq m \leq 10^5 )), representing the number of nodes and edges respectively. The next ( m ) lines each contain three integers ( u ), ( v ), ( w ) (( 1 \leq u, v \leq n ); ( -10^9 \leq w \leq 10^9 )), indicating a directed edge from node ( u ) to node ( v ) with weight ( w ).

outputFormat

Output a single line containing either "YES" if there is a cycle with a positive total weight, or "NO" if there is no such cycle.## sample

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

YES