ICPC Teams

You coach the ICPC club at your university. The club has $3N$ students, and you have to build $N$ teams for the next ICPC. Every ICPC team has exactly 3 members, and each student belongs to exactly one team.

When you build the teams you have to account for several relationships among the students. Two students who get along extremely well perform much better when they share a team. The opposite happens for a pair that gets along badly. So two students with a good relationship must be placed on the same team, and two students with a bad relationship must be placed on different teams. As the coach you know all $M$ relationships among the students.

Write a program that counts the team assignments satisfying every condition. Two assignments are different if and only if there is a pair of students who share a team in one assignment and do not share a team in the other.

The first line contains two integers $N$ and $M$ ($1 \le N \le 10^6$, $1 \le M \le 18$). The $i$-th of the next $M$ lines contains three integers $A_i$, $B_i$ ($1 \le A_i, B_i \le 3N$, $A_i \ne B_i$) and $C_i$ ($C_i \in \{0, 1\}$). $A_i$ and $B_i$ are student numbers and $C_i$ is the relationship type. If $C_i$ is 0, student $A_i$ and student $B_i$ have a good relationship. If $C_i$ is 1, they have a bad relationship. For all $1 \le i, j \le M$ with $i \ne j$, $\{A_i, B_i\} \ne \{A_j, B_j\}$ holds.

Print the number of valid team assignments modulo $10^9 + 9$ on one line.