ICPC 팀 구성

당신은 대학 ICPC 동아리의 코치다. 동아리에는 학생 $3N$명이 있고, 다음 ICPC에 내보낼 팀 $N$개를 만들어야 한다. ICPC의 모든 팀은 3명으로 이루어지고, 각 학생은 정확히 한 팀에 속한다.

팀을 짤 때는 학생 사이의 관계를 여러 가지 고려해야 한다. 사이가 아주 좋은 두 학생이 같은 팀이 되면 성적이 눈에 띄게 오른다. 사이가 나쁜 두 학생이 같은 팀이 되면 그 반대의 일이 벌어진다. 그래서 사이가 좋은 두 학생은 반드시 같은 팀에 넣고, 사이가 나쁜 두 학생은 반드시 다른 팀에 넣는다. 코치인 당신은 학생 사이의 관계 $M$개를 모두 알고 있다.

조건을 모두 만족하는 팀 구성이 몇 가지인지 세는 프로그램을 작성하라. 두 팀 구성은 어떤 두 학생이 한쪽에서는 같은 팀이고 다른 쪽에서는 다른 팀일 때, 그리고 그때만 서로 다르다고 본다.

첫째 줄에 정수 $N$과 $M$이 주어진다 ($1 \le N \le 10^6$, $1 \le M \le 18$). 이어지는 $M$개 줄 중 $i$번째 줄에는 정수 $A_i$, $B_i$ ($1 \le A_i, B_i \le 3N$, $A_i \ne B_i$)와 $C_i$ ($C_i \in \{0, 1\}$)가 주어진다. $A_i$와 $B_i$는 학생의 번호이고, $C_i$는 관계의 종류다. $C_i$가 0이면 $A_i$번 학생과 $B_i$번 학생은 사이가 좋고, 1이면 사이가 나쁘다. $i \ne j$인 모든 $1 \le i, j \le M$에 대해 $\{A_i, B_i\} \ne \{A_j, B_j\}$가 성립한다.

조건을 만족하는 팀 구성의 수를 $10^9 + 9$로 나눈 나머지를 한 줄에 출력한다.