// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
const int N = 209, M = 50004;
int n, m, U[M], V[M], C[M], DR[M], P[N];
bool MR[N], Mark[M];
long long F[N], D[N][N];
vector < int > Adj[N];
inline long long SSSP(int st, int fn, int j)
{
memset(F, 63, sizeof(F));
memset(MR, 0, sizeof(MR));
F[st] = 0;
for (int __ = 1; __ <= n; __ ++)
{
int v = -1;
for (int i = 1; i <= n; i ++)
if (!MR[i] && (v == -1 || F[v] > F[i]))
v = i;
MR[v] = 1;
for (int i : Adj[v])
if (i != j && F[V[i]] > F[v] + C[i])
F[V[i]] = F[v] + C[i];
if (v == V[j])
if (F[U[j]] > F[v] + C[j])
F[U[j]] = F[v] + C[j];
}
return (F[fn]);
}
inline long long Solve(int st, int fn)
{
memset(P, 0, sizeof(P));
memset(F, 63, sizeof(F));
memset(MR, 0, sizeof(MR));
memset(Mark, 0, sizeof(Mark));
F[st] = 0;
for (int __ = 1; __ <= n; __ ++)
{
int v = -1;
for (int i = 1; i <= n; i ++)
if (!MR[i] && (v == -1 || F[v] > F[i]))
v = i;
MR[v] = 1;
for (int i : Adj[v])
if (F[V[i]] > F[v] + C[i])
F[V[i]] = F[v] + C[i],
P[V[i]] = i;
}
long long Mn = LLONG_MAX;
if (!P[fn])
return (Mn);
int v = fn;
while (v != st)
Mark[P[v]] = 1, v = U[P[v]];
for (int i = 1; i <= m; i ++)
if (!Mark[i])
Mn = min(Mn, D[fn][V[i]] + C[i] + D[U[i]][st] + DR[i] + F[fn]);
for (int j = 1; j <= m; j ++)
if (Mark[j])
Mn = min(Mn, SSSP(st, fn, j) + SSSP(fn, st, j) + DR[j]);
return (Mn);
}
int main()
{
scanf("%d%d", &n, &m);
memset(D, 63, sizeof(D));
for (int i = 1; i <= m; i ++)
{
scanf("%d%d%d%d", &U[i], &V[i], &C[i], &DR[i]);
D[U[i]][V[i]] = min(D[U[i]][V[i]], 1LL * C[i]);
Adj[U[i]].push_back(i);
}
for (int i = 1; i <= n; i ++)
D[i][i] = 0;
for (int k = 1; k <= n; k ++)
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
long long Mn = D[1][n] + D[n][1];
for (int i = 1; i <= m; i ++)
if (D[1][V[i]] + C[i] + D[U[i]][n] < D[1][n] && D[n][V[i]] + C[i] + D[U[i]][1] < D[n][1])
Mn = min(Mn, D[1][V[i]] + C[i] + D[U[i]][n] + D[n][V[i]] + C[i] + D[U[i]][1] + DR[i]);
Mn = min(Mn, Solve(1, n));
Mn = min(Mn, Solve(n, 1));
if (Mn > (long long)(1e10) * n)
Mn = -1;
return !printf("%lld\n", Mn);
}
