//In the name of God
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef pair<lli,lli> pii;
typedef vector<lli> ve;
typedef vector<pii> vp;
const lli N=4e5+100;
const lli mod=1e9+7;//998244353;//1e9+9
const lli INF=1e18;
lli power(lli x,lli y){lli res = 1;x = x % mod;while(y>0){if( y & 1 ){res = (res * x) % mod;}y = y >> 1;x = (x * x)%mod;}return res;}
#define all(v) v.begin(),v.end()
#define debug(x) cerr << (#x) << " " << (x) << endl
#define MP make_pair
#define PB push_back
#define fi first
#define se second
#define FOR(x,n) for(int x = 0; x < n; x++)
#define FORS(x,n) for(int x = 1; x <= n; x++)
#define TEST int TQPWIEJR; cin>>TQPWIEJR;while(TQPWIEJR--)
#define endl "\n"
int n,m;
vp E;
lli pos[N],A[N],ps[N];
ve L[N];
lli solve(lli in){
lli p = 1;
pos[in] = 1;
A[p++] = in;
for(lli i = (in == n ? 1 : in+1); i != in; i = (i == n ? 1 : i+1)){
A[p++] = i;
pos[i] = p-1;
}
for(auto [a,b] : E){
if(pos[a] > pos[b])swap(a,b);
a = pos[a],b = pos[b];
L[a].PB(b);
ps[a] += 1;
ps[b] -= 1;
}
FORS(i,n)ps[i] += ps[i-1];
lli ans = 0;
multiset<lli> S;
multiset<pii> H;
FORS(i,n-1){
for(auto j : L[i])H.insert(MP(j,i));
while(S.size() && *S.begin()<=i){S.erase(S.begin());}
while(H.size() && (*H.begin()).fi<=i){H.erase(H.begin());}
while((lli)S.size()*2 < ps[i]){
if(H.empty())return INF;
pii P = *H.rbegin();
H.erase(H.find(P));
S.insert(P.fi);
ans ++;
}
}
FOR(i,n+1){
L[i].clear();
pos[i] = A[i] = ps[i] = 0;
}
return ans;
}
int main(){
ios_base::sync_with_stdio(false),cout.tie(0), cin.tie(0);
cin>>n>>m;
FOR(i,m){
lli a,b,c;
cin>>a>>b>>c;
E.PB(MP(a,b));
}
lli ans = INF;
FORS(i,2){
ans = min(ans,solve(i));
}
cout<<ans<<endl;
}
