1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<iostream>
#include<set>

using namespace std;

const int MAXN = 1000 * 1000;
const int MAXM = 1000 * 1000;
const int MAXDRZEWO = 2 * (2 << 19) + 1;

int N;
int n, m;

set<int> drzewo[MAXDRZEWO];

void add(int a, int b, int barwa)
{
	a = N + a;
	b = N + b;
	
	if (barwa == 1)
		barwa = 2;
	else if (barwa == 2)
		barwa = 3;
	else
		barwa = 5;
	//2 = żółty
	//3 = niebieksi
	//5 = czerwony
	//Wyniki mnożenia barw 6 = zielony i dalej liczyć nie trzeba

	drzewo[a].insert(barwa);
	drzewo[b].insert(barwa);

	while (a / 2 != b / 2)
	{
		if (a % 2 == 0)
			drzewo[a + 1].insert(barwa);
		if (b % 2 == 1)
			drzewo[b - 1].insert(barwa);

		a /= 2; b /= 2;
	}
}

bool get(int x)
{
	x = N + x;
	int wynik = 1;
	set<int> finalnafarba;
	while (x>1)
	{
		for (auto it = drzewo[x].begin(); it != drzewo[x].end(); it++)
			finalnafarba.insert(*it);
		x /= 2;
	}
	for (auto it = finalnafarba.begin(); it != finalnafarba.end(); it++)
		wynik *= *it;
	if (wynik == 6)
		return true;
	return false;
}

void zaladoj_drzewo()
{
	N = 2;
	while (N<n)
	{
		N *= 2;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	cin >> m;
	zaladoj_drzewo();

	for (int i = 0; i < m; i++)
	{
		int l, r, k;
		cin >> l >> r >> k;
		l -= 1, r -= 1;
		add(l, r, k);
	}
	int suma = 0;
	for (int i = 0; i < n; i++)
	{
		if (get(i))
			suma++;
	}
	cout << suma << endl;
	return 0;
}