#include <bits/stdc++.h>

using namespace std;

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];
    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;
    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]]++;
    }
    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]] == 1 && 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];
                    st.insert({dp[a[i] + b[i] - v], a[i] + b[i] - v});
                } else if (dp[a[i] + b[i] - v] > dp[v] + p[i]) {
                    st.erase({dp[a[i] + b[i] - v], a[i] + b[i] - v});
                    dp[a[i] + b[i] - v] = dp[v] + p[i];
                    last[a[i] + b[i] - v] = (int) 1e18;
                    st.insert({dp[a[i] + b[i] - v], a[i] + b[i] - v});
                }
            } else if (dp[a[i] + b[i] - v] > dp[v] + p[i]) {
                st.erase({dp[a[i] + b[i] - v], a[i] + b[i] - v});
                dp[a[i] + b[i] - v] = dp[v] + p[i];
                last[a[i] + b[i] - v] = (int) 1e18;
                st.insert({dp[a[i] + b[i] - v], a[i] + b[i] - v});
            }
        }
    }
    cout << (dp[n - 1] == (int) 1e18 ? -1 : dp[n - 1]);
    return 0;
}