#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,t[505],a[505],b[505],s[505];
int dis[505],vis[505],cnt[505],l,r,sl,sr;
int d[505][505];
struct node
{
	int v,w,x;
};
struct edge
{
	int l,x;
}last[505];
int check(int mid)
{
	vector<node>v[505];
	memset(d,0,sizeof(d));
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(cnt,0,sizeof(cnt));
	queue<int>q;
	for(int i=1;i<=m;i++)
	{
		if(t[i]==1)
		{
			if(a[i]<=b[i])
			{
				a[i]--;
				v[b[i]].push_back({a[i],-s[i],0});
				a[i]++;
			}
			else 
			{
				swap(a[i],b[i]);
				a[i]--;
				v[a[i]].push_back({b[i],mid-s[i],1});
				a[i]++;
				swap(a[i],b[i]);
			}
		}
		else 
		{
			if(a[i]<=b[i])
			{
				a[i]--;
				v[a[i]].push_back({b[i],s[i],0});
				a[i]++;
			}
			else 
			{
				swap(a[i],b[i]);
				a[i]--;
				v[b[i]].push_back({a[i],s[i]-mid,-1}); 
				a[i]++;
				swap(a[i],b[i]);
			}
		}
	}
	for(int i=0;i<=n;i++)
	{
		if(i!=0)v[i].push_back({i-1,-1});
		q.push(i);
		vis[i]=1;
		dis[i]=0;
	}
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		vis[t]=0;
		for(auto i:v[t])
		{
			if(dis[i.v]>dis[t]+i.w)
			{
				dis[i.v]=dis[t]+i.w;
				cnt[i.v]=cnt[t]+1;
				last[i.v]={t,i.x};
				if(cnt[i.v]>n)
				{
					int k=0;
					bool f[505]={};
					for(int j=i.v;;j=last[j].l)
					{
						if(f[j])break;
						k+=last[j].x;
						f[j]=true;
					}	
					return k;
				}
				if(!vis[i.v])
				{
					vis[i.v]=1;
					q.push(i.v);
				}
			}
		}
	}
	return 1e18;
}
void findl()
{
	l=1,r=1e12;
	while(l<r)
	{
		int mid=(l+r)/2;
		int x=check(mid);
		if(x==1e18)r=mid;
		else if(x<0)r=mid-1;
		else l=mid+1;
	}
	sl=r;
}
void findr()
{
	l=1,r=1e12;
	while(l<r)
	{
		int mid=(l+r+1)/2;
		int x=check(mid);
		if(x==1e18)l=mid;
		else if(x<0)r=mid-1;
		else l=mid+1;
	}
	sr=l;
} 
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)cin>>t[i]>>a[i]>>b[i]>>s[i];
	if(check(0)==0)
	{
		cout<<-1;
		return 0;
	}
	findl();
	findr();
	cout<<sr-sl+1;
	return 0;
}