#include <bits/stdc++.h>
#define ent '\n'
#define int long long

// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

typedef long long ll;
using namespace std;

const int maxn = 1e5 + 12;
const int inf = (int)1e12 + (int)1e8;

int cost[202][202];
int u[maxn], v[maxn], w[maxn], c[maxn];
int d1[maxn], dn[maxn];
bool used[maxn];
int n, m, k;

void work(int ver, int d[]) {
    for(int i = 1; i <= n; i++) {
        d[i] = inf;
        used[i] = false;
    }
    d[ver] = 0;
    for(int t = 0; t < n; t++) {
        int v = 0;
        for(int i = 1; i <= n; i++) {
            if((!v || d[i] < d[v]) && !used[i]) {
                v = i;
            }
        }
        if(!v || d[v] == inf) break;
        used[v] = true;
        for(int i = 1; i <= n; i++) {
            if(cost[v][i] < inf) {
                d[i] = min(d[i], d[v] + cost[v][i]);
            }
        }
    }
}

void solve() {
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        cin >> u[i] >> v[i] >> w[i] >> c[i];
    }
    int ans = inf;
    for(int pos = 0; pos <= m; pos++) {
        swap(u[pos], v[pos]);
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                cost[i][j] = inf;
            }
            cost[i][i] = 0;
        }
        for(int i = 1; i <= m; i++) {
            cost[u[i]][v[i]] = min(cost[v[i]][u[i]], w[i]);
        }

        work(1, d1);
        work(n, dn);

        if(d1[n] < inf && dn[1] < inf) {
            ans = min(ans, d1[n] + dn[1] + c[pos]);
        }
        swap(u[pos], v[pos]);
    }
    if(ans >= inf) ans = -1;
    cout << ans << ent;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}