#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;
template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}
const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 200 + 7;
const ll oo = 1e18 + 69;
const int maxe = 5e4 + 7;
int n, m;
pa trace[maxn][maxn];
ll c[maxn][maxn], c2[maxn][maxn], best_without_u[maxe];
struct edge {
int u, v, c, d;
} ed[maxe];
bool used[maxe];
ll solve(int s, int t) {
vector<pa> path;
for(int i = 1; i <= m; i++) {
best_without_u[i] = oo;
used[i] = 0;
}
int p = s;
while(p != t) {
path.pb({p, trace[p][t].se});
used[trace[p][t].se] = 1;
p = trace[p][t].fi;
}
path.pb({t, 0});
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) c2[i][j] = (i == j ? 0:oo);
}
for(int i = 1; i <= m; i++) {
if(used[i]) continue;
best_without_u[i] = c[s][t];
mini(c2[ed[i].u][ed[i].v], ed[i].c);
}
for(int k = 1; k <= n; k++) {
for(int u = 1; u <= n; u++) {
for(int v = 1; v <= n; v++) mini(c2[u][v], c2[u][k] + c2[k][v]);
}
}
for(int i = 0; i < Size(path) - 1; i++) {
for(int j = 0; j <= i; j++) {
for(int k = j + 1; k < Size(path); k++) {
int u = path[j].fi;
int v = path[k].fi;
mini(best_without_u[path[i].se], c[s][u] + c2[u][v] + c[v][t]);
}
}
}
ll ans = oo;
for(int i = 1; i <= m; i++) {
int u = ed[i].u, v = ed[i].v;
mini(ans, best_without_u[i] + c[t][v] + c[u][s] + ed[i].c + ed[i].d);
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen(TASK".inp", "r", stdin);
//freopen(TASK".out", "w", stdout);
cin>>n>>m;
for(int i = 1; i <= m; i++) {
cin>>ed[i].u>>ed[i].v>>ed[i].c>>ed[i].d;
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
c[i][j] = (i == j ? 0:oo);
trace[i][j] = {j, 0};
}
}
for(int i = 1; i <= m; i++) {
if(mini(c[ed[i].u][ed[i].v], ed[i].c)) trace[ed[i].u][ed[i].v].se = i;
}
for(int k = 1; k <= n; k++) {
for(int u = 1; u <= n; u++) {
for(int v = 1; v <= n; v++) {
if(mini(c[u][v], c[u][k] + c[k][v])) trace[u][v] = trace[u][k];
}
}
}
ll ans = oo;
mini(ans, c[1][n] + c[n][1]);
mini(ans, solve(1, n));
mini(ans, solve(n, 1));
cout<<(ans == oo ? -1:ans);
return 0;
}
