워크샵으로 가는 버스에 타고 안녕.

월간 향유회의 운영진들은 $3$행 $N$열의 직사각형 모양 버스를 타고 워크샵에 가려고 한다. 버스의 $1$행과 $3$행의 각 칸에는 좌석과 에어컨이 있다. 한 칸의 에어컨을 가동하면 그 칸과 변을 공유하는 모든 칸이 시원해진다. 운영진은 총 $M$명이며, 각 운영진은 버스의 한 좌석에 앉아 그 칸의 에어컨 가동 여부를 정한다. 모든 운영진은 서로 다른 좌석에 앉는다.

버스의 에어컨 시스템을 관리하는 당신은, 운영진이 앉지 않은 좌석의 에어컨을 마음대로 가동할 수 있다. 버스를 쾌적하게 유지하기 위해, 당신은 $2$행을 포함한 모든 칸을 시원하게 만들고 싶다. 버스의 모든 칸을 시원하게 하기 위해 가동해야 하는 에어컨의 최소 개수를 구하라. 이때 운영진이 직접 가동한 에어컨도 개수에 포함한다.

첫째 줄에 버스의 열의 개수 $N$과 운영진의 수 $M$이 공백으로 구분되어 주어진다. $(1 \le M \le 2 \times N \le 400\,000)$

다음 $M$개의 줄에 걸쳐 각 운영진의 정보가 $x_i$, $y_i$, $t_i$의 순서로 공백으로 구분되어 주어진다. $i$번째 운영진은 ($x_i$, $y_i$) 칸에 앉는다. $t_i = 1$이면 그 칸의 에어컨을 가동하고, $t_i = 0$이면 가동하지 않는다. $(x_i \in \{1, 3\};\ 1 \le y_i \le N;\ t_i \in \{0, 1\})$

모든 운영진은 서로 다른 좌석에 앉고, 모든 입력은 정수이다.

버스의 모든 칸을 시원하게 하기 위해 가동해야 하는 에어컨의 최소 개수를 출력한다. 어떻게 가동하더라도 모든 칸을 시원하게 할 수 없다면 -1을 출력한다.