#include <iostream>
#include <queue>
using namespace std;
int maxi = 0, maxi_pos = 0;
const int MAXN = 2e5 + 4;
vector<int> konce[MAXN];
int sumy[MAXN];
int n, m, a, b, c;
bool check(int maxi_val, int k) {
priority_queue<int> kolejka;
int ile_usunalem = 0;
vector<int> sumy2(n + 2, 0);
for (int i = 1; i <= maxi_pos; i++) {
for (int k : konce[i]) kolejka.push(k);
int wzorek = sumy[i] - maxi_val + (k - (sumy[i] + maxi_val) + 1) / 2;
while (wzorek > ile_usunalem && kolejka.size()) {
int koniec = kolejka.top();
kolejka.pop();
ile_usunalem++;
sumy2[maxi_pos]--;
sumy2[koniec + 1] ++;
}
if (wzorek > ile_usunalem) return 0;
}
for (int i = maxi_pos + 1; i <= n; i++) {
sumy2[i] += sumy2[i - 1];
if (sumy2[i] + sumy[i] > maxi_val) return 0;
}
return 1;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
vector<pair<int, int>> prz;
for (int i = 0; i < m; i++) {
cin >> a >> b >> c;
if (a > b) swap(a, b);
b--;
prz.push_back({a, b});
sumy[a]++;
sumy[b + 1] --;
}
for (int i = 1; i <= n; i++) {
sumy[i] += sumy[i - 1];
if (maxi > sumy[i]) maxi_pos = i;
maxi = max(sumy[i], maxi);
}
for (int i = 0; i < m; i++) {
if (prz[i].first <= i && prz[i].second >= i) konce[prz[i].first].push_back(prz[i].second);
}
for (int i = 0; i <= n; i++) {
sort(konce[i].begin(), konce[i].end());
}
int left = 0, right = maxi;
while (left < right) {
int mid = (left + right) / 2;
if (check(mid, maxi - mid) || check(mid, maxi - mid + 1)) right = mid;
else left = mid + 1;
}
cout << left << '\n';
return 0;
}
