#include <bits/stdc++.h>
using namespace std;
// * No One Dies a Virgin, Life Fucks Us All
typedef long long ll;
#define nl '\n'
#define ff first
#define ss second
#define pb push_back
#define sik(x) {cout << x << nl; return;}
constexpr ll maxn = 2e5+10, mod = 1e9 + 7, inf = 1e17, SQ = 450, LG = 20;
typedef pair<int, int> pii;
int n, m, l[maxn], r[maxn], add[maxn], a[maxn];
vector<int> E[maxn];
multiset<int> st;
inline bool chk(int p, int x, int r) {
if (r > x || r < 0) return 0;
st.clear();
fill(add, add + n + 1, 0);
int cnt = 0;
for (int i = 1 ; i <= p ; i ++) {
int need = (a[i] - x + r + 1) / 2;
for (int j : E[i]) if (j >= p) st.insert(j);
while (cnt < need) {
if (st.empty()) return 0;
++ cnt;
auto R = prev(st.end());
add[0] ++;
add[i] -= 2;
add[*R + 1] += 2;
st.erase(R);
}
}
for (int i = 0 ; i <= n - 1 ; i ++) {
if (i >= 1) add[i] += add[i - 1];
if (a[i] + add[i] > x) return 0;
}
return 1;
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
if (n > 3000 || m > 3000) return 0;
for (int i = 1, c ; i <= m ; i ++) {
cin >> l[i] >> r[i] >> c;
if (c != 1) return 0;
if (l[i] > r[i]) swap(l[i], r[i]);
a[l[i]] += c;
a[r[i]] -= c;
E[l[i]].pb(r[i] - 1);
}
for (int i = 1 ; i <= n ; i ++) a[i] += a[i - 1];
int ans = m;
for (int p = 1 ; p <= n-1 ; p ++) {
int l = 0, r = a[p] + 1;
while (r - l > 1) {
int mid = (l + r) >> 1;
if (chk(p, mid, a[p] - mid) || chk(p, mid, a[p] - mid + 1)) r = mid;
else l = mid;
}
if (r != a[p] + 1) ans = min(ans, r);
}
cout << ans << nl;
}
