#pragma GCC optimize("Ofast")
#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()
struct fenwick {
int n;
vector<int> t;
explicit fenwick(int _n) : n(_n) {
t.resize(n + 1, 0);
}
void update(int v, int delta) {
for (; v <= n; v += v & (-v)) {
t[v] += delta;
}
}
void add_on_segment(int l, int r, int delta) {
l++, r++;
update(l, delta);
update(r + 1, -delta);
}
int get_value(int v) {
v++;
int result = 0;
for (; v > 0; v -= v & (-v)) {
result += t[v];
}
return result;
}
};
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;
fenwick cnt(n);
for (int left_border = 0; left_border < n; left_border++) {
for (auto right_border : have[left_border]) {
cnt.add_on_segment(left_border, right_border, 1);
}
}
bool ok = true;
int already_flipped = 0;
for (int i = 0; i + 1 < n; i++) {
int need_flip = max(0, (cnt.get_value(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());
cnt.add_on_segment(left_border, right_border, -1);
cnt.add_on_segment(0, left_border - 1, 1);
cnt.add_on_segment(right_border + 1, n - 1, 1);
}
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.get_value(i) > mid) {
ok = false;
break;
}
}
if (ok) {
can = true;
break;
}
}
if (can) {
r = mid;
} else {
l = mid;
}
}
cout << r << '\n';
}
