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