Uolevi has stumbled upon an ancient online feud. The feud is probably about that one TV show that has multiple endings since people are talking about little and big ends. There would seem to be a clear divide between little-endians and big-endians but Uolevi wishes to double check this fact by analyzing the like & dislike statistics.

There are $n$ users numbered $1,2,\dots,n$ on the site and $m$ dislikes/likes. The $i$-th dislike/like was from user $a_i$ about user $b_i$'s comment and was of type $c_i$. If it was a like, then $c_i = 1$, otherwise $c_i = -1$. Uolevi wants to check whether the users can be split into two groups where the members of one group have only liked or received likes from their own group and only disliked or received dislikes from the opposite group. One of the groups may be empty.

Input

The first line contains two integers $n$ and $m$. The $i$-th of next $m$ following line contains three integers $a_i,\,b_i,$ and $c_i$.

Output

Print "Yes" if there is a clear division and "No" otherwise.

Constraints

• $2 \le n \le 10^5$
• $1 \le m \le 2 \times 10^5$
• $1 \le a_i, b_i \le n$
• $a_i \neq b_i$
• $c_i = 1$ or $c_i = -1$

Example 1

Input:

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

Output:

Yes

Example 2

Input:

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

Output:

No