#include <bits/stdc++.h>
#define INF 1000000000000000000
#define N 100005
#define M 200005
using namespace std;
typedef long long ll;

int n, m;
ll cnt[M], ans=INF;
vector <int> to[N];
vector <ll> dp[N][2];

struct es { int u, v, c, p, idu, idv; } e[M];

struct Pnt
{
    int u, tg, id; ll dst;
    bool operator< (const Pnt &x) const { return dst>x.dst; }
};

void Dij ()
{
    priority_queue <Pnt> q;

    for (int i=0; i<(int)to[1].size(); i++) {
        int eid=to[1][i];
        cnt[e[eid].c]+=e[eid].p;
    }
    for (int i=0; i<(int)to[1].size(); i++) {
        int eid=to[1][i];
        int u=(e[eid].u==1 ? e[eid].v : e[eid].u);
        int id=(e[eid].u==1 ? e[eid].idv : e[eid].idu);
        int c=e[eid].c, p=e[eid].p;

        dp[u][0][id]=cnt[c]-p;
        dp[u][1][id]=p;
        q.push((Pnt){ u, 0, id, dp[u][0][id] });
        q.push((Pnt){ u, 1, id, dp[u][1][id] });
    }
    for (int i=0; i<(int)to[1].size(); i++) {
        int eid=to[1][i];
        cnt[e[eid].c]-=e[eid].p;
    }

    while (!q.empty()) {
        int u=q.top().u, tg=q.top().tg, idu=q.top().id;

        if (u==n) { ans=min(ans, dp[u][tg][idu]); }

        q.pop();

        for (int i=0; i<(int)to[u].size(); i++) {
            int eid=to[u][i];
            if (tg && idu==i) { continue; }
            cnt[e[eid].c]+=e[eid].p;
        }
        for (int i=0; i<(int)to[u].size(); i++) {
            int eid=to[u][i];
            if (i==idu) { continue; }

            int v=(e[eid].u==u ? e[eid].v : e[eid].u);
            int idv=(e[eid].u==u ? e[eid].idv : e[eid].idu);
            int c=e[eid].c, p=e[eid].p;

            if (dp[u][tg][idu]+cnt[c]-p < dp[v][0][idv]) {
                dp[v][0][idv]=dp[u][tg][idu]+cnt[c]-p;
                q.push((Pnt){ v, 0, idv, dp[v][0][idv] });
            }
            if (dp[u][tg][idu]+p < dp[v][1][idv]) {
                dp[v][1][idv]=dp[u][tg][idu]+p;
                q.push((Pnt){ v, 1, idv, dp[v][1][idv] });
            }
        }
        for (int i=0; i<(int)to[u].size(); i++) {
            int eid=to[u][i];
            if (tg && idu==i) { continue; }
            cnt[e[eid].c]-=e[eid].p;
        }
    }
}

int main ()
{
    // freopen("0test.in", "r", stdin);
    // freopen("0test.out", "w", stdout);

    scanf("%d %d", &n, &m);
    for (int i=1; i<=m; i++) {
        int u, v, c, p; scanf("%d %d %d %d", &u, &v, &c, &p);
        to[u].push_back(i); to[v].push_back(i);
        e[i]=(es){ u, v, c, p, to[u].size()-1, to[v].size()-1 };
    }

    for (int u=1; u<=n; u++) {
        for (int i=0; i<(int)to[u].size(); i++) {
            dp[u][0].push_back(INF);
            dp[u][1].push_back(INF);
        }
    }

    Dij();

    if (ans==INF) { printf("-1\n"); }
    else { printf("%lld\n", ans); }

    return 0;
}