#include <iostream>
using namespace std;
int const N=3e3+10;
int n,m;
int a[N],b[N],c[N];
// int St[4*N]={};
// int lazy[4*N]={};
// int fen[N]={};
// void push(int i)
// {
// for (int j=2*i;j<=2*i+1;j++)
// {
// lazy[j]+=lazy[i];
// St[j]+=lazy[i];
// }
// lazy[i]=0;
// }
// void reset(int i,int st,int en)
// {
// St[i]=lazy[i]=0;
// if (st==en)
// return;
// int mid=(st+en)/2;
// reset(i*2,st,mid);
// reset(i*2+1,mid+1,en);
// }
// void update(int i,int st,int en,int l,int r,int val)
// {
// if (l>r)
// return;
// if (st>=l&&en<=r)
// {
// lazy[i]+=val;
// St[i]+=val;
// return;
// }
// if (st>r||en<l)
// return;
// int mid=(st+en)/2;
// push(i);
// update(i*2,st,mid,l,r,val);
// update(i*2+1,mid+1,en,l,r,val);
// St[i]=max(St[i*2],St[i*2+1]);
// }
// int get(int i,int st,int en,int l,int r)
// {
// if (l>r)
// return 0;
// if (st>=l&&en<=r)
// return St[i];
// if (st>r||en<l)
// return 0;
// push(i);
// int mid=(st+en)/2;
// return max(get(i*2,st,mid,l,r),get(i*2+1,mid+1,en,l,r));
// }
inline void solve()
{
cin>>n>>m;
for (int i=0;i<m;i++)
{
cin>>a[i]>>b[i]>>c[i];
a[i]--;b[i]--;
}
int mx=1e3;
int cnt[n]={};
for(int i=0;i<(1<<m);i++)
{
for (int i=0;i<n;i++)
cnt[i]=0;
int mf=0;
for (int j=0;j<m;j++)
{
if((1<<j)&i)
{
if (a[j]<b[j])
{
for (int k=a[j];k<b[j];k++)
cnt[k]++;
}
else
{
for (int k=a[j];k<n;k++)
cnt[k]++;
for (int k=0;k<b[j];k++)
cnt[k]++;
}
}
else
{
if (a[j]<b[j])
{
for (int k=0;k<a[j];k++)
cnt[k]++;
for (int k=b[j];k<n;k++)
cnt[k]++;
}
else
{
for (int k=b[j];k<a[j];k++)
cnt[k]++;
}
}
}
for (int j=0;j<n;j++)
mf=max(mf,cnt[j]);
mx=min(mx,mf);
}
cout<<mx<<endl;
// for (int i=0;i<m;i++)
// {
// if (a[i]<b[i])
// {
// int z=get(1,0,n-1,a[i],b[i]-1);
// int f=max(get(1,0,n-1,0,a[i]-1),get(1,0,n-1,b[i],n-1));
// if (z==f)
// {
// if (b[i]-a[i]>=a[i]+(n-1-b[i]+1))
// {
// cout<<i<<endl;
// update(1,0,n-1,a[i],b[i]-1,c[i]);
// }
// else
// {
// update(1,0,n-1,0,a[i]-1,c[i]);
// update(1,0,n-1,b[i],n-1,c[i]);
// }
// }
// else
// {
// if (z<f)
// {
// cout<<i<<endl;
// update(1,0,n-1,a[i],b[i]-1,c[i]);
// }
// else
// {
// update(1,0,n-1,0,a[i]-1,c[i]);
// update(1,0,n-1,b[i],n-1,c[i]);
// }
// }
// }
// else
// {
// int z=get(1,0,n-1,b[i],a[i]-1);
// int f=max(get(1,0,n-1,0,b[i]-1),get(1,0,n-1,a[i],n-1));
// if (z==f)
// {
// if (a[i]-b[i]>b[i]+(n-1-a[i]+1))
// update(1,0,n-1,b[i],a[i]-1,c[i]);
// else
// {
// update(1,0,n-1,0,b[i]-1,c[i]);
// update(1,0,n-1,a[i],n-1,c[i]);
// }
// }
// else
// {
// if (z<f)
// update(1,0,n-1,b[i],a[i]-1,c[i]);
// else
// {
// update(1,0,n-1,0,b[i]-1,c[i]);
// update(1,0,n-1,a[i],n-1,c[i]);
// }
// }
// }
// }
// for (int i=0;i<n;i++)
// {
// cout<<get(1,0,n-1,i,i)<<endl;
// }
// cout<<get(1,0,n-1,0,n-1)<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t=1;
for (int i=1;i<=t;i++)
{
solve();
}
}
