#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
signed main() {
#ifdef PC
freopen("input.txt", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> have(n);
for (int i = 0; i < m; i++) {
int from, to, cnt;
cin >> from >> to >> cnt;
from--, to--;
if (from > to) {
swap(from, to);
}
if (from < to) {
have[from].push_back(to - 1);
}
}
int l = -1, r = m;
while (r - l > 1) {
int mid = (l + r) / 2;
bool can = false;
for (int cnt_flip = 0; cnt_flip <= mid; cnt_flip++) {
multiset<pair<int, int>> segments;
vector<int> cnt(n);
for (int left_border = 0; left_border < n; left_border++) {
for (auto right_border : have[left_border]) {
cnt[left_border]++;
cnt[right_border + 1]--;
}
}
for (int i = 1; i < n; i++) {
cnt[i] += cnt[i - 1];
}
bool ok = true;
int already_flipped = 0;
for (int i = 0; i + 1 < n; i++) {
int need_flip = max(0, (cnt[i] + (cnt_flip - already_flipped) - mid + 1) / 2);
if (already_flipped + need_flip > cnt_flip) {
ok = false;
break;
}
for (auto right_border : have[i]) {
segments.insert({right_border, i});
}
if (SZ(segments) < need_flip) {
ok = false;
break;
}
for (int j = 0; j < need_flip; j++) {
auto [right_border, left_border] = *segments.rbegin();
segments.erase(--segments.end());
//BAD!!!
for (int k = 0; k < n; k++) {
if (k >= left_border && k <= right_border) {
cnt[k]--;
} else {
cnt[k]++;
}
}
}
while (!segments.empty() && segments.begin()->first < i + 1) {
segments.erase(segments.begin());
}
already_flipped += need_flip;
}
for (int i = 0; i < n; i++) {
if (cnt[i] > mid) {
ok = false;
break;
}
}
if (ok) {
can = true;
break;
}
}
if (can) {
r = mid;
} else {
l = mid;
}
}
cout << r << '\n';
}
