#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second
using namespace std;
const int inf = 1e18;
int n;
int dp[510][510], ds[510];
int a[50010], b[50010], w[50010], c[50010];
vector<int> adj[510];
bool vis[510];
void fmn(int &a, int b) {a = min(a, b);}
void fmx(int &a, int b) {b = max(a, b);}
int dij(int s, int t) {
fill(ds, ds + n + 1, inf);
fill(vis, vis + n, false);
ds[s] = 0;
for (int i = 0; i < n; i++) {
int u = n;
for (int v = 0; v < n; v++) if (!vis[v] && ds[v] < ds[u]) u = v;
vis[u] = 1;
if (ds[u] == inf) break ;
for (int e: adj[u]) fmn(ds[b[e]], ds[u] + w[e]);
}
return ds[t];
}
void solve () {
int m; cin >> n >> m;
for (int u = 0; u < n; u++)
for (int v = 0; v < n; v++)
dp[u][v] = (u == v ? 0 : inf);
for (int e = 0; e < m; e++) {
cin >> a[e] >> b[e] >> w[e] >> c[e], --a[e], --b[e];
fmn(dp[a[e]][b[e]], w[e]);
adj[a[e]].pb(e);
}
for (int w = 0; w < n; w++)
for (int u = 0; u < n; u++)
for (int v = 0; v < n; v++)
fmn(dp[u][v], dp[u][w] + dp[w][v]);
int s = 0, t = n - 1, ans = dp[s][t] + dp[t][s];
for (int e = 0; e < m; e++) {
int to = min(dp[s][t], dp[s][b[e]] + w[e] + dp[a[e]][t]);
int fr = min(dp[t][s], dp[t][b[e]] + w[e] + dp[a[e]][s]);
if (c[e] + to + fr < ans) {
adj[a[e]].erase(find(all(adj[a[e]]), e));
swap(a[e], b[e]);
adj[a[e]].pb(e);
fmn(ans, c[e] + dij(s, t) + dij(t, s));
adj[a[e]].pp();
swap(a[e], b[e]);
adj[a[e]].pb(e);
}
}
cout << (ans < inf ? ans : -1);
}
signed main() {IOS solve(); return 0;}
