#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)2e9 + (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 <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cost[i][j] = inf;
        }
        cost[i][i] = 0;
    }
    for(int i = 1; i <= m; i++) {
        cin >> u[i] >> v[i] >> w[i] >> c[i];
        cost[u[i]][v[i]] = w[i];
    }
    work(1, d1);
    work(n, dn);
    int ans = d1[n] + dn[1];
    for(int i = 1; i <= m; i++) {
        int dist1 = d1[n], distn = dn[1];
        dist1 = min(dist1, d1[v[i]] + dn[u[i]] + w[i]);
        distn = min(distn, dn[v[i]] + d1[u[i]] + w[i]);
        ans = min(ans, dist1 + distn + c[i]);
    }
    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();
    }
}