#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)(x).size()
#define trav(x, a) for (const auto& x: a)
#define pii pair<int,int>
#define st first
#define nd second
using namespace std;
typedef long long ll;
const int N = 5e4 + 5;
const ll inf = 0x1f1f1f1f1f1f1f1f;
vector<int> e[2][N], adj[N];
int U[N], V[N], C[N], D[N];
ll dp[2][2][N], dp2[2][205][205];
int n, m, par[2][2][N];
int mrk[2][2][N];
vector<int> path[2][2];
void solve(int s, int t, int i) {
priority_queue<pii,vector<pii>,greater<pii>> pq;
pq.push({0, s});
for (int j = 1; j <= n; j++)
dp[i][s>1][j] = inf;
dp[i][s>1][s] = 0;
while (!pq.empty()) {
auto c = pq.top(); pq.pop();
if (dp[i][s>1][c.nd] != c.st)
continue;
for (int j: e[i][c.nd]) {
int v = U[j]^V[j]^c.nd;
if (dp[i][s>1][v] > c.st + C[j]) {
dp[i][s>1][v] = c.st + C[j];
par[i][s>1][v] = j;
pq.push({dp[i][s>1][v], v});
}
}
}
if (dp[i][s>1][t] == inf)
return;
int u = t;
while (u != s) {
int j = par[i][s>1][u];
mrk[i][s>1][j] = 1;
path[i][s>1].pb(u);
u = U[j]^V[j]^u;
}
path[i][s>1].pb(u);
reverse(path[i][s>1].begin(), path[i][s>1].end());
}
ll calc(int j, int i) {
int mi = n+1;
for (int l = 0; l+1 < sz(path[0][j]); l++) {
if (U[i] == path[0][j][l] && path[0][j][l+1] == V[i]) {
mi = l;
break;
}
}
ll ret = inf;
for (int l = 0; l <= mi; l++)
for (int r = mi+1; r < sz(path[0][j]); r++)
ret = min(ret, dp[0][j][path[0][j][l]] + dp2[j][path[0][j][l]][path[0][j][r]] + dp[1][j^1][path[0][j][r]]);
return ret;
}
int main() {
memset(dp, 0x1f, sizeof dp);
memset(dp2, 0x1f, sizeof dp2);
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d %d %d %d", U+i, V+i, C+i, D+i);
e[0][U[i]].pb(i);
e[1][V[i]].pb(i);
}
for (int i = 0; i < 2; i++) {
solve(1, n, i);
solve(n, 1, i);
}
for (int t = 0; t < 2; t++) {
for (int i = 1; i <= m; i++) if (!mrk[0][t][i])
dp2[t][U[i]][V[i]] = min(dp2[t][U[i]][V[i]], 1ll*C[i]);
for (int i = 1; i <= n; i++)
dp2[t][i][i] = 0;
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dp2[t][i][j] = min(dp2[t][i][j], dp2[t][i][k] + dp2[t][k][j]);
}
ll x1 = dp[0][0][n], x2 = dp[0][1][1];
ll ans = x1 + x2;
for (int i = 1; i <= m; i++) {
bool f1 = mrk[0][0][i], f2 = mrk[0][1][i];
ll c1 = min(x1, dp[0][0][V[i]] + C[i] + dp[1][1][U[i]]);
ll c2 = min(x2, dp[0][1][V[i]] + C[i] + dp[1][0][U[i]]);
if (f1 && f2)
ans = min(ans, calc(0,i) + calc(1,i) + D[i]);
else if (f1)
ans = min(ans, calc(0,i) + c2 + D[i]);
else if (f2)
ans = min(ans, calc(1,i) + c1 + D[i]);
else
ans = min(ans, c1 + c2 + D[i]);
}
if (ans >= inf)
ans = -1;
printf("%I64d\n", ans);
}
