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

문제

월간 향유회의 운영진들은 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을 대신 출력한다.

제한

힌트