/*
ID: espr1t
TASK: 
KEYWORDS: 
*/

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
FILE *in; FILE *out;

const int MAX = 1048576;
const int TREE = MAX * 2;

struct Link {
    int left, right;
    Link() {
        left = right = -1;
    }
};

int n, m;
int a[MAX];
int ops[MAX][3];
Link list[MAX];
int tree[TREE];

int query(int idx1, int idx2) {
    if (idx2 < idx1)
        return 0;
    idx1 += (TREE >> 1); idx2 += (TREE >> 1);
    if (idx1 == idx2)
        return tree[idx1];
    int ret = 0;
    ret = max(ret, tree[idx1]); bool flag1 = !(idx1 & 1); idx1 >>= 1;
    ret = max(ret, tree[idx2]); bool flag2 =  (idx2 & 1); idx2 >>= 1;
    while (idx1 != idx2) {
        if (flag1) ret = max(ret, tree[(idx1 << 1) | 1]);
        if (flag2) ret = max(ret, tree[(idx2 << 1) | 0]);
        flag1 = !(idx1 & 1); idx1 >>= 1;
        flag2 =  (idx2 & 1); idx2 >>= 1;
    }
    return ret;
}

void update(int idx, int val) {
    idx += (TREE >> 1);
    while (idx != 0) {
        tree[idx] = max(tree[idx], val);
        idx >>= 1;
    }
}

int lis() {
    int ans = 0;
    for (int i = n - 1; i >= 0; i--) {
        int cur = query(0, a[i] - 1) + 1;
        ans = max(ans, cur);
        update(a[i], cur);
    }
    return ans;
}

void remove(int idx) {
    list[list[idx].left].right = list[idx].right;
    list[list[idx].right].left = list[idx].left;
}

void addLeft(int idx1, int idx2) {
    if (list[idx1].left == idx2)
        return;
    
    list[idx2].left = list[idx1].left;
    list[list[idx1].left].right = idx2;
    list[idx2].right = idx1;
    list[idx1].left = idx2;
//    fprintf(stderr, " -- moved %d to the left of %d (replaced %d)\n", idx2, idx1, list[idx2].left);
}

void addRight(int idx1, int idx2) {
    if (list[idx1].right == idx2)
        return;
    list[idx2].right = list[idx1].right;
    list[list[idx1].right].left = idx2;
    list[idx2].left = idx1;
    list[idx1].right = idx2;
//    fprintf(stderr, " -- moved %d to the right of %d (replaced %d)\n", idx2, idx1, list[idx2].right);
}

int main(void) {
	in = stdin; out = stdout;
	in = fopen("sequence.in", "rt"); out = fopen("sequence.out", "wt");
	
	fscanf(in, "%d %d", &n, &m);
	
	for (int i = 0; i <= n + 1; i++) {
	    list[i].left = i - 1;
	    list[i].right = i + 1;
	}
	
	for (int i = 0; i < m; i++) {
	    fscanf(in, "%d %d %d", &ops[i][0], &ops[i][1], &ops[i][2]);
        remove(ops[i][1] + 1);
	    if (ops[i][0] == 1) {
	        addRight(ops[i][2] + 1, ops[i][1] + 1);
	    } else {
	        addLeft(ops[i][2] + 1, ops[i][1] + 1);
	    }
	}
	
	int size = 0;
	for (int node = list[0].right; node != n + 1; node = list[node].right) {
	    a[size++] = node - 1;
	}
	
	/*
	for (int i = 0; i < n; i++) {
	    fprintf(stdout, "%d%c", a[i], i + 1 == n ? '\n' : ' ');
	}
	*/
	
	fprintf(out, "%d\n", n - lis());
	return 0;
}