#include <bits/stdc++.h>
using namespace std;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false)
const int MAX_N = 2e5 + 5;
const int MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
const int LOG = 30;
int n, m;
pair<int, int> al[MAX_N];
vector<int> st[MAX_N];
bool check(int x)
{
for (int i = 0; i <= x; i++)
{
if (i > 10 && i < x - 3) continue;
int sum = 0;
multiset<int> rem;
priority_queue<int> used;
for (int j = 0; j < n - 1; j++)
{
for (int x : st[j]) rem.insert(x);
rem.erase(j);
while (used.size() && used.top() == -j) used.pop();
int mi = (rem.size() + used.size() + i + 1 - x) / 2 - used.size();
if ((int) rem.size() < mi)
{
sum = INF;
break;
}
for (int pp = 0; pp < mi; pp++)
{
int ind = (*rem.rbegin());
sum++;
rem.erase(rem.find(ind));
used.push(-ind);
}
}
if (sum <= i) return true;
}
return false;
}
void solve() {
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int p;
cin >> al[i].first >> al[i].second >> p;
al[i].first--, al[i].second--;
if (al[i].first > al[i].second) swap(al[i].first, al[i].second);
st[al[i].first].push_back(al[i].second);
}
int l = -1;
int r = m;
while (r - l > 1)
{
int mid = (r + l) >> 1;
if (check(mid)) r = mid;
else l = mid;
}
cout << r << "\n";
}
int main() {
sui;
int tc = 1;
//cin >> tc;
for (int t = 1; t <= tc; t++) {
solve();
}
}
