Problem Statement

There are $N$ people. Each person is either "honest" or a "liar".

There are $Q$ claims. The $i$-th claim was made by person $A_i$. The content of the claim is as follows.

• $($ When $C_i=0$ $)$ Person $B_i$ is "honest".
• $($ When $C_i=1$ $)$ Person $B_i$ is a "liar".

There are $2^N$ combinations of who among the $N$ people is "honest" and who is a "liar". Find the number of these combinations that do not contradict any of the claims, modulo $998244353$.

・About the claims

An "honest" person claims that an "honest" person is "honest", and claims that a "liar" is a "liar".

A "liar" claims that an "honest" person is a "liar", and claims that a "liar" is "honest".

Input

$N\ \ Q$
$A_1\ \ B_1\ \ C_1$
$A_2\ \ B_2\ \ C_2$
$:$
$A_Q\ \ B_Q\ \ C_Q$

• $2 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq A_i,B_i \leq N$
• $A_i \neq B_i$
• $(A_i, B_i) \neq (A_j, B_j) \ (i \neq j)$
• $C_i$ is $0$ or $1$
• All inputs are integers

Output

Output the value you found, followed by a newline.

Sample

4 3
1 2 1
2 3 1
3 1 0

4

3 3
1 2 1
2 3 1
3 1 1

0

172 12
13 29 0
48 127 1
86 25 0
171 68 1
21 67 1
29 86 0
37 23 0
37 163 1
45 48 1
163 127 0
2 13 0
68 22 1

346915093