H. Depoimentos compatíveis

Time limit: 5000 msMemory limit: 256 MB

Há $n$ pessoas, cada uma pertencente a um de dois grupos. Não sabemos a qual grupo cada pessoa pertence. Recebemos $m$ depoimentos em uma ordem fixa. Cada depoimento afirma que duas pessoas pertencem ao mesmo grupo ou a grupos diferentes.

Um trecho contíguo de depoimentos é compatível se existe alguma atribuição das pessoas aos dois grupos que torna verdadeiros todos os depoimentos desse trecho. A atribuição pode ser diferente para trechos diferentes. Grupos vazios são permitidos.

Conte os trechos contíguos não vazios compatíveis. Depoimentos repetidos são permitidos. Uma pessoa pode aparecer nas duas posições de um depoimento; nesse caso, a afirmação deve ser interpretada literalmente.

Input

A primeira linha contém $n,m$ ( $1\le n\le100\,000$ ; $1\le m\le50\,000$ ). Cada uma das próximas $m$ linhas contém $u,v,b$ ( $1\le u,v\le n$ ; $b\in\{0,1\}$ ). O valor $b=0$ afirma que $u$ e $v$ estão no mesmo grupo; $b=1$ afirma que estão em grupos diferentes.

Output

Imprima a quantidade de trechos compatíveis.

Samples

Sample 1

Input

Output

Cada trecho próprio é compatível. Os três depoimentos juntos exigiriam três pessoas em grupos dois a dois diferentes, o que é impossível.

Sample 2

Input

1 2
1 1 0
1 1 1

Output

Apenas o trecho formado pelo primeiro depoimento é compatível.