#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(); } }