409661: GYM103671 B Village Bridge 2

In the great Unovan sea, there are $$$n$$$ ($$$2 \leq n \leq 2600$$$) villages labeled $$$1$$$ through $$$n$$$, each of which is located on an island. There are currently $$$m$$$ ($$$0 \leq m \leq \min(n(n - 1), 2600)$$$) bidirectional magic bridges, each of which connects two distinct villages.

Magic bridges come in two types — day bridges and night bridges. As their name implies, day bridges can only be crossed during the daytime, and night bridges can only be crossed at night. Crossing any bridge takes the entire duration of its active period (for example, crossing a night bridge takes the entire night). Two villages are said to be connected if it is possible to continuously travel from one village to the other without stopping for a day or night to pass.

Please determine whether every single pair of villages is connected or not.

The first line consists of two space-separated integers $$$n$$$ ($$$2 \leq n \leq 2600$$$) and $$$m$$$ ($$$0 \leq m \leq \min(n(n - 1), 2600)$$$).

The following $$$m$$$ lines contain the descriptions of each bridge. The $$$i$$$th line contains $$$3$$$ space-separated integers $$$u, v, w$$$ ($$$1 \leq u, v \leq n, u \neq v, 0 \leq w \leq 1$$$), indicating that there is a bridge connecting villages $$$u$$$ and $$$v$$$. If $$$w = 0$$$, the bridge is a day bridge, otherwise it is a night bridge.

For any pair of villages, it is guaranteed that there is at most one bridge of each type connecting them.

On a single line, output the string YES if all pairs of villages are connected, and NO otherwise.

3 3
1 2 1
2 3 1
1 3 1

YES

4 5
1 2 0
1 3 0
2 4 1
3 4 0
3 4 1

YES

4 0

NO

In the first test case, all pairs of villages are directly connected using night bridges.

In the second test case, the bridges form a square and satisfy the condition. For example, villages $$$2$$$ and $$$3$$$ are connected due to the following path: we can begin at village $$$2$$$ at night. We can cross the night bridge from village $$$2$$$ to $$$4$$$, and it is daytime now. We can then cross the day bridge from village $$$4$$$ to $$$3$$$.

In the third test case, no pair of villages is connected, since there are no bridges.