Reachability in a Directed Graph with Mixed Roads

You are given a directed graph with n cities and m roads. Each road connects two different cities and has a type. For a road represented by the tuple \( (u,v,t) \), if \( t = 1 \), the road goes from city \( u \) to city \( v \) only; if \( t = 2 \), the road can be traversed in both directions.

Your task is to determine whether every city is reachable from every other city.

Formally: Given \( n \) and \( m \), followed by \( m \) triples \( (u,v,t) \), determine if for every ordered pair of cities \( (i,j) \), there is a path from \( i \) to \( j \). Output "YES" if the graph is strongly connected, and "NO" otherwise.

inputFormat

The first line contains two integers \( n \) and \( m \) separated by space \( (1 \leq n \leq 10^5, 0 \leq m \leq 10^5) \), representing the number of cities and roads respectively.

Each of the next \( m \) lines contains three integers \( u, v, t \). Here, \( u \) and \( v \) are the cities connected by a road and \( t \) represents the type of the road. If \( t = 1 \), the road is one-way from \( u \) to \( v \); if \( t = 2 \), the road is bidirectional.

outputFormat

Output a single line containing "YES" (without quotes) if every city is reachable from any other city, or "NO" otherwise.

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

YES