#include <bits/stdc++.h>

using namespace std;
#define int long long

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    int c[m], p[m], dp[n], last[n], a[m], b[m], ind[n];
    vector<int> g[n];
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v >> c[i] >> p[i];
        u--, v--;
        a[i] = u, b[i] = v;
        g[u].emplace_back(i);
        g[v].emplace_back(i);
    }
    for (int i = 0; i < n; i++) dp[i] = last[i] = (int) 1e18, ind[i] = 0;
    dp[0] = 0;
    set<pair<int, int>> st;
    map<int, int> cnt[n];
    for (int i = 0; i < n; i++) {
        for (auto u: g[i])
            cnt[i][c[u]] += p[u];
    }
    st.insert({dp[0], 0});
    while (!st.empty()) {
        int v = st.begin()->second;
        st.erase(st.begin());
        for (auto i: g[v]) {
            if (c[i] != last[v]) {
                if (cnt[v][c[i]] == p[i] && dp[a[i] + b[i] - v] > dp[v]) {
                    st.erase({dp[a[i] + b[i] - v], a[i] + b[i] - v});
                    dp[a[i] + b[i] - v] = dp[v];
                    last[a[i] + b[i] - v] = c[i];
                    ind[a[i] + b[i] - v] = i;
                    st.insert({dp[a[i] + b[i] - v], a[i] + b[i] - v});
                } else if (dp[a[i] + b[i] - v] > dp[v] + min(p[i], cnt[v][c[i]] - p[i])) {
                    st.erase({dp[a[i] + b[i] - v], a[i] + b[i] - v});
                    dp[a[i] + b[i] - v] = dp[v] + min(p[i], cnt[v][c[i]] - p[i]);
                    if (dp[a[i] + b[i] - v] == dp[v] + p[i])
                        last[a[i] + b[i] - v] = (int) 1e18;
                    else last[a[i] + b[i] - v] = c[i], ind[a[i] + b[i] - v] = i;
                    st.insert({dp[a[i] + b[i] - v], a[i] + b[i] - v});
                }
            } else {
                if (ind[v] != i)
                    cnt[v][c[i]] -= p[ind[v]];
                if (dp[a[i] + b[i] - v] > dp[v] + min(p[i], cnt[v][c[i]] - p[i])) {
                    st.erase({dp[a[i] + b[i] - v], a[i] + b[i] - v});
                    dp[a[i] + b[i] - v] = dp[v] + min(p[i], cnt[v][c[i]] - p[i]);
                    if (dp[a[i] + b[i] - v] == dp[v] + p[i] - p[i])
                        last[a[i] + b[i] - v] = (int) 1e18;
                    else last[a[i] + b[i] - v] = c[i], ind[a[i] + b[i] - v] = i;
                    st.insert({dp[a[i] + b[i] - v], a[i] + b[i] - v});
                }
                if (ind[v] != i)
                    cnt[v][c[i]] += p[ind[v]];
            }
        }
    }
    cout << (dp[n - 1] == (int) 1e18 ? -1 : dp[n - 1]);
    return 0;
}