#include <bits/stdc++.h>
#define R(x) x = read()
#define ENDL push('\n');
#define SPACE push(' ');
#define int long long
using namespace std;
char pbuf[1<<20], *pp=pbuf;
inline void push(const char &c) {
	if(pp - pbuf == 1<<20)fwrite(pbuf, 1, 1<<20, stdout),pp = pbuf;
	*pp++ = c;
}
class io {public:~io() {fwrite(pbuf, 1, pp - pbuf, stdout);}} _;
inline void write(int x) {
	if (x<0)x=-x,push('-');
	int sta[35],top=0;
	do {
		sta[top++]=x%10,x/=10;
	} while (x);
	while(top)push(sta[--top]^'0');
}
inline int read() {
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return x*f;
}
constexpr int N=300100;
int siz[N],ch[N][2],val[N],fix[N],tot,s[N];
int rt,x,y,z;
int newnode(int v){
	++tot;
	s[tot]=v;
	siz[tot]=1;
	val[tot]=v;
	fix[tot]=rand();
	return tot;
}
void update(int i){siz[i]=siz[ch[i][0]]+siz[ch[i][1]]+1,s[i]=s[ch[i][0]]+s[ch[i][1]]+val[i];}
void split(int i,int k,int&x,int&y){
	if(!i)x=y=0;
	else{
		if(val[i]<=k){
			x=i;
			split(ch[i][1],k,ch[i][1],y);
		}else{
			y=i;
			split(ch[i][0],k,x,ch[i][0]);
		}
		update(i);
	}
}
int merge(int x,int y){
	if(!x||!y)return x|y;
	else{
		if(fix[x]<fix[y]){
			ch[x][1]=merge(ch[x][1],y);
			update(x);
			return x;
		}else{
			ch[y][0]=merge(x,ch[y][0]);
			update(y);
			return y;
		}
	}
}
void insert(int val){
	split(rt,val,x,y);
	rt=merge(merge(x,newnode(val)),y);
}
void del(int val){
	split(rt,val,x,y);
	split(x,val-1,x,z);
	z=merge(ch[z][0],ch[z][1]);
	rt=merge(x,merge(z,y));
}
int kvl(int val){
	split(rt,val-1,x,y);
	int k=siz[x];
	rt=merge(x,y);
	return k+1;
}
int kth(int i,int k){
	while(1){
		if(k<=siz[ch[i][0]])i=ch[i][0];
		else if(siz[ch[i][0]]+1==k)return i;
		else k-=(siz[ch[i][0]]+1),i=ch[i][1];
	}
}
int mid(int rt){return val[kth(rt,siz[rt]/2)];}
//int cb(){
//	split(rt,mid(rt)-1,x,y);
//	int s1=s[x],sz=siz[x];
//	rt=merge(x,y);
//	sz=siz[rt]/2-sz;
//	return s[rt]-2*s1-2*mid(rt)*sz;
//}
int q(int val){
	int sz=siz[rt]/2,r=0;
	split(rt,val-1,x,y);
	r=s[x]*2+val*(sz-siz[x])*2;
	rt=merge(x,y);
	return r;
}
int cb(){
	int val=mid(rt);
	return s[rt]-q(val);
}
int n,s1,nn,ans[N],k;
struct peo{
	int a,b;
}r[N];
signed main(){
	R(k);R(n);
	for(int i=1;i<=n;i++){
		char p,q;
		cin >> p;
		R(int s);
		cin >> q;
		R(int t);
		if(s<t)s^=t^=s^=t;
		if(p==q)s1+=s-t;
		else{
			s1++;
			nn++;
			r[nn]=peo{t,s};
		}
	}
	n=nn;
	sort(r+1,r+1+n,[](peo x,peo y){
		return x.a+x.b<y.b+y.b;
	});
	for(int i=1;i<=n;i++){
		insert(r[i].a);
		insert(r[i].b);
		ans[i]+=cb();
	}
	if(k==1){
		write(ans[n]+s1);
		return 0;
	}
	for(int i=0;i<=tot;i++)ch[i][0]=ch[i][1]=0;
	rt=tot=0;
	for(int i=n;i>0;i--){
		insert(r[i].a);
		insert(r[i].b);
		ans[i-1]+=cb();
	}
	int mi=ans[n];
	for(int i=1;i<=n;i++){
		mi=min(mi,ans[i]);
	}
	write(mi+s1);
    return 0;
}