#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 
const i64 INF = 1e18; 

int n, m; 
i64 g[205][205], h[205][205], f[205][205];
bool vis[205]; 

void Dijkstra(int S, i64 *d, int *fa) {
    for (int i = 1; i <= n; ++i) d[i] = INF, vis[i] = 0;
    d[S] = 0; 
    for (int op = 1; op < n; ++op) {
        int x = 0; 
        for (int i = 1; i <= n; ++i) if (!vis[i] && (x == 0 || d[i] < d[x])) x = i;
        vis[x] = 1; 
        for (int y = 1; y <= n; ++y) if (d[y] > d[x] + g[x][y]) d[y] = d[x] + g[x][y], fa[y] = x;
    }
}

i64 d1[205], sid1[205], dn[205], sidn[205], dist[205]; 
int fat[205], fa1[205], af1[205], fan[205], afn[205]; 
int u[50005], v[50005]; 
i64 c[50005], d[50005]; 
i64 ans = INF; 

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> m, memset(g, 0x3f, sizeof(g)), memset(f, 0x3f, sizeof(f));
    for (int i = 1; i <= m; ++i) {
        cin >> u[i] >> v[i] >> c[i] >> d[i]; 
        if (c[i] <= g[u[i]][v[i]]) f[u[i]][v[i]] = g[u[i]][v[i]], g[u[i]][v[i]] = c[i]; 
        else f[u[i]][v[i]] = min(f[u[i]][v[i]], c[i]); 
    }
    Dijkstra(1, d1, fa1), Dijkstra(n, dn, fan); 
    ans = min(ans, d1[n] + dn[1]); 
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) h[i][j] = g[i][j]; 
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) g[i][j] = h[j][i]; 
    Dijkstra(1, sid1, af1), Dijkstra(n, sidn, afn); 
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) g[i][j] = h[i][j]; 

    for (int i = 1; i <= m; ++i) {
        i64 tmpa = g[u[i]][v[i]], tmpb = g[v[i]][u[i]];
        g[u[i]][v[i]] = f[u[i]][v[i]]; g[v[i]][u[i]] = min(g[v[i]][u[i]], c[i]); 

        i64 p = 0;
        if (fa1[v[i]] != u[i] || d1[u[i]] + c[i] != d1[v[i]]) p = min(d1[n], d1[v[i]] + c[i] + sidn[u[i]]); 
        else Dijkstra(1, dist, fat), p = dist[n]; 
        i64 q = 0;
        if (fan[v[i]] != u[i] || dn[u[i]] + c[i] != dn[v[i]]) q = min(dn[1], dn[v[i]] + c[i] + sid1[u[i]]); 
        else Dijkstra(n, dist, fat), q = dist[1]; 

        g[u[i]][v[i]] = tmpa; g[v[i]][u[i]] = tmpb; 
        ans = min(ans, p + q + d[i]); 
    }
    cout << (ans == INF ? -1 : ans) << "\n"; 
    
    return 0;
}