//In the name of God
#include<bits/stdc++.h>
/*MHN*/
using namespace std;
typedef long long int lli;
typedef long double ld;
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;}
lli modinv(lli x){return power(x,mod-2);}
lli divide(lli x,lli y){return ((x%mod) * modinv(y))%mod;}
#define all(v) v.begin(),v.end()
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define migmig ios_base::sync_with_stdio(false),cout.tie(0), cin.tie(0);
#define read freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define debug(x) cerr << (#x) << " " << (x) << endl
#define MP make_pair
#define PB push_back
#define fi first
#define se second
#define SUM(v) accumulate(v.begin(),v.end(), 0LL)
#define FOR(x,n) for(lli x = 0; x < n; x++)
#define FORS(x,n) for(lli x = 1; x <= n; x++)
#define TEST int TQPWIEJR; cin>>TQPWIEJR;while(TQPWIEJR--)
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define sep " "
lli tmp;
lli n,m;
vp E;
ve adj[N];
bool vis[N];
lli ps[N];
lli L;
lli get_dis(lli r){
lli l =L;
if(l > r){
return n-l + r;
}
return r-l;
}
lli solve(lli in){
multiset<lli> S;
lli ans = 0;
for(lli i = in;; i = (i < n ? i+1 : 1)){
L = i;
vis[i] = 1;
while(S.find(i)!=S.end())S.erase(S.find(i));
ps[i] += ps[(i == 1 ? n : i-1)];
ve ca;
for(auto j : adj[i]){
if(vis[j] == 0){
ca.PB(j);
ps[i] += 1;
ps[j] -= 1;
}
}
sort(all(ca),[](lli x,lli y){
return get_dis(x) < get_dis(y);
});
lli p = 0;
while(p < (lli)ca.size() && (lli)S.size()*2 < ps[i]-1){
S.insert(ca[p++]);
}
ans += ca.size() - p;
if(i == (in == 1 ? n : in-1))break;
}
FORS(i,n)vis[i] = 0,ps[i]= 0;
return ans;
}
int main(){
migmig;
cin>>n>>m;
FOR(i,m){
lli a,b,c;
cin>>a>>b>>c;
E.PB(MP(a,b));
adj[a].PB(b);
adj[b].PB(a);
}
lli ans = INF;
FORS(i,n){
ans = min(ans,solve(i));
}
cout<<ans<<endl;
}
