#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int MAXN = 500 + 10;
const ll inf = 1e12;

int n,m;
vector <tuple <int,ll,int> > G[MAXN];
int vis[MAXN],cnt[MAXN],pre[MAXN],lst[MAXN];
ll dis[MAXN];

int dfs(int h) {
    int u=h,sum=0;
    memset(vis,0,sizeof vis);
    do { u=pre[u],vis[u]=1;} while(!vis[u]);
    h=u;
    do { sum+=lst[u],u=pre[u];} while(u!=h);
    if(sum==0) cout<<-1<<'\n',exit(0);
    return (sum>0 ? 1 : -1);
}

int spfa(ll C) {
    int s=n+1;
    for(int i=1;i<=n+1;i++) 
        dis[i]=inf,vis[i]=0,cnt[i]=0,pre[i]=0;

    queue <int> Q;
    Q.push(s);
    dis[s]=0,vis[s]=1,cnt[s]++;

    while(!Q.empty()) {
        int u=Q.front();
        Q.pop();
        vis[u]=0;
        for(auto [v,val,k] : G[u]) 
            if(dis[v]>dis[u]+val+(ll)k*C) {
                dis[v]=dis[u]+val+(ll)k*C;
                pre[v]=u,lst[v]=k;
                if(!vis[v]) {
                    vis[v]=1;
                    Q.push(v);
                    cnt[v]++;
                    if(cnt[v]>n+1)
                        return dfs(v);
                }
            }
    }
    return 0;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        int op,s,t;
        ll l; 
        cin>>op>>s>>t>>l;
        if(op==1) {
            if(s<t) G[t].push_back({s,-l,0});
            else G[t].push_back({s,-l,1});
        }
        else if(op==2) {
            if(s<t) G[s].push_back({t,l,0});
            else G[s].push_back({t,l,-1});
        }
    }

    for(int i=1;i<=n-1;i++)
        G[i+1].push_back({i,-1,0});
    G[1].push_back({n,-1,1});

    for(int i=1;i<=n;i++) 
        G[n+1].push_back({i,0,0});
    
    ll ansl,ansr;
    ll l=0,r=inf;
    while(l<r) {
        ll mid=(l+r)>>1;
        int tp=spfa(mid);
        if(!tp) l=mid;
        else if(tp==1) l=mid+1;
        else if(tp==-1) r=mid-1;
    }
    ansr=l;

    if(ansr>=inf) {
        cout<<-1<<'\n';
        return 0;
    }
    
    l=0,r=inf;
    while(l<r) {
        ll mid=(l+r)>>1;
        int tp=spfa(mid);
        if(!tp) r=mid;
        else if(tp==1) l=mid+1;
        else if(tp==-1) r=mid-1;
    }
    ansl=l;

    cout<<ansr-ansl+1<<'\n';

    return 0;
}