#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
struct _clog{
    template<class T>
    _clog operator<<(T x){
#ifndef ONLINE_JUDGE
        cerr<<"\033[33m"<<x<<"\033[0m";
#endif
        return *this;
    }
}mlog;
using tiii=tuple<ll,ll,ll>;
vector<tiii> g[550];
ll n;
ll dis[550];
ll cnt[550];
bool inq[550];
ll pre[550][2];
bool vis[550];
ll tk[550];
ll spfa(ll x){
    for(ll i=1;i<=n;i++)dis[i]=1e12,cnt[i]=0,inq[i]=0,vis[i]=0,pre[i][0]=0,tk[i]=0;
    queue<ll> q;
    q.push(1);dis[1]=0;inq[1]=1;
    while(!q.empty()){
        ll nw=q.front();
        q.pop();
        inq[nw]=0;
        for(auto [i,j,k]:g[nw]){
            if(dis[i]>dis[nw]+k*x+j){
                dis[i]=dis[nw]+k*x+j;
                if(!inq[i]){
                    //mlog<<i<<"\n";
                    inq[i]=1;
                    cnt[i]++;
                    q.push(i);
                    pre[i][0]=nw;
                    pre[i][1]=k;
                    if(cnt[i]>=n){
                        ll nww=i;
                        ll ans=0;
                        while(1){
                            vis[nww]=1;
                            ll nxt=pre[nww][0];
                            ll tmp=pre[nww][1]+tk[nww];
                            if(vis[nxt])return (tmp-tk[nxt]>0?1:-1);
                            nww=nxt;
                            tk[nww]=tmp;
                        }
                    }
                    
                }
            }
        }
    }
    for(ll i=1;i<=n;i++)mlog<<dis[i]<<" ";
    return 0;
}
int main(){
    ios::sync_with_stdio(0);
    ll m;
    cin>>n>>m;
    for(ll i=1;i<n;i++)g[i].push_back({i+1,-1,0});
    g[n].push_back({1,-1,1});
    for(ll i=1;i<=m;i++){
        ll o,s,t,l;
        cin>>o>>s>>t>>l;
        if(o==1){
            if(s<t)g[s].push_back({t,-l,0});
            else g[s].push_back({t,-l,1});
        }else{
            if(s<t)g[t].push_back({s,l,0});
            else g[t].push_back({s,l,-1});
        }
    }
    // for(ll i=1;i<=n;i++){
    //     for(auto [z,j,k]:g[i]){
    //         mlog<<i<<"->"<<z<<" +"<<j<<" *"<<k<<"\n";
    //     }
    // }
    // 
    mlog<<spfa(11)<<"\n";
    ll L,R;
    ll l=1,r=1e14;
    while(l<=r){
        ll mid=(l+r)>>1;
        ll rt=spfa(mid);
        if(rt==0)R=mid,l=mid+1;
        else if(rt==-1)r=mid-1;
        else l=mid+1;
    }
    if(R>=9.9e13){
        cout<<"-1\n";
        return 0;
    }
    l=1,r=1e14;
    while(l<=r){
        ll mid=(l+r)>>1;
        ll rt=spfa(mid);
        if(rt==0)L=mid,r=mid-1;
        else if(rt==1)l=mid+1;
        else r=mid-1;
    }
    cout<<R-L+1;
    return 0;
}