Aboard the Bus to the Workshop, Hello

Staff of 월간 향유회 are riding a bus shaped like a rectangle with $3$ rows and $N$ columns to a workshop. Each cell in rows $1$ and $3$ has a seat and an air conditioner. Turning on the air conditioner in a cell cools that cell and every cell that shares a side with it. There are $M$ staff members in total, and each one sits in a seat on the bus and decides whether to turn on the air conditioner in that cell. All staff sit in different seats.

You manage the bus's air conditioning system and may turn on the air conditioners in seats that no staff member occupies. To keep the bus comfortable, you want every cell, including those in row $2$, to be cooled. Find the minimum number of air conditioners that must be turned on to cool every cell of the bus. Air conditioners turned on by staff members count toward this number too.

The first line contains the number of columns $N$ and the number of staff members $M$, separated by a space. $(1 \le M \le 2 \times N \le 400\,000)$

The next $M$ lines each contain $x_i$, $y_i$, and $t_i$, separated by spaces. Staff member $i$ sits in cell $(x_i, y_i)$. If $t_i = 1$, that staff member turns on the air conditioner in that cell. If $t_i = 0$, it stays off. $(x_i \in \{1, 3\};\ 1 \le y_i \le N;\ t_i \in \{0, 1\})$

All staff sit in different seats, and all input values are integers.

Print the minimum number of air conditioners that must be turned on to cool every cell of the bus. If no way of turning them on cools every cell, print -1 instead.