rt.

#include <cstring>
#include <iostream>
#include <queue>

#define len(x) (w[x] + k[x] * mid)

using namespace std;

const int N = 5e2 + 10, M = 1e3 + 10;

int n, m;
int h[N], e[M], ne[M], w[M], k[M], idx;
long long ll, rr;
long long dis[N];
int cnt[N], preu[N], pree[N];
bool st[N], dfsst[N];
int dfscnt[N];

inline void speedup()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

inline void add(int a, int b, int c, int d)
{
    e[++idx] = b;
    w[idx] = c, k[idx] = d;
    ne[idx] = h[a];
    h[a] = idx;
}

inline int dfs(int u, int tot)
{
    if (dfsst[u])
        return tot < dfscnt[u] ? 1 : -1;
    return dfsst[u] = 1, dfscnt[u] = tot, dfs(preu[u], tot + k[pree[u]]);
}

inline int spfa(long long mid)
{
    memset(dis, 0, sizeof dis);
    memset(cnt, 0, sizeof cnt);
    memset(st, 1, sizeof st);
    queue<int> q;
    for (int i = 1; i <= n; i++)
        q.push(i);
    while (!q.empty())
    {
        int tmp = q.front();
        q.pop();
        st[tmp] = 0;
        for (int i = h[tmp]; i; i = ne[i])
        {
            int j = e[i];
            if (dis[j] > dis[tmp] + len(i))
            {
                dis[j] = dis[tmp] + len(i), preu[j] = tmp, pree[j] = i;
                if ((cnt[j] = cnt[tmp] + 1) >= n)
                    return memset(dfsst, 0, sizeof dfsst), dfs(j, 0);
                if (!st[j])
                    q.push(j), st[j] = 1;
            }
        }
    }
    return 0;
}

int main()
{
    speedup();
    cin >> n >> m;
    while (m--)
    {
        int type, s, t, l;
        cin >> type >> s >> t >> l;
        if (type == 1)
        {
            if (t > s)
                add(t, s, -l, 0);
            else
                add(t, s, -l, 1);
        }
        else
        {
            if (t > s)
                add(s, t, l, 0);
            else
                add(s, t, l, -1);
        }
    }
    for (int i = 2; i <= n; i++)
        add(i, i - 1, -1, 0);
    if (spfa(5e11 + 1) <= 0)
    {
        cout << -1 << endl;
        return 0;
    }
    long long l = 0, r = 5e11 + 1;
    while (l + 1 ^ r)
    {
        long long mid = l + r >> 1;
        if (spfa(mid) >= 0)
            r = mid;
        else
            l = mid;
    }
    ll = r;
    l = 0, r = 5e11 + 1;
    while (l + 1 ^ r)
    {
        long long mid = l + r >> 1;
        if (spfa(mid) <= 0)
            l = mid;
        else
            r = mid;
    }
    rr = l;
    cout << rr - ll + 1 << endl;
    return 0;
}