#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
#ifdef DEBUG
#define debug(args...) _debug(args)
void _debug(const char* format, ...) {
va_list args;
va_start(args, format);
vprintf(format, args);
va_end(args);
}
#else
#define debug(args...)
#endif
#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 205
#define MAXM 50005
int n, m;
ll g[MAXN][MAXN], sg[MAXN][MAXN];
int u[MAXM], v[MAXM], c[MAXM], d[MAXM];
ll rdist[MAXN][MAXN];
bool visited[MAXN];
bool onshot[MAXN][MAXN];
ll dist[MAXN][MAXN];
int p[MAXN];
void dij(int s, bool up = 0) {
REP (i, 1, n + 1) {
dist[s][i] = LINF;
visited[i] = 0;
p[i] = -1;
}
dist[s][s] = 0;
REP (_, 0, n) {
ll u = -1, mn = LINF;
REP (i, 1, n + 1) {
if (!visited[i] && mnto(mn, dist[s][i])) {
u = i;
}
}
if (u == -1) break;
visited[u] = 1;
REP (i, 1, n + 1) {
if (mnto(dist[s][i], dist[s][u] + g[u][i]) && up) {
onshot[u][i] = 1;
if (p[i] != -1) {
onshot[p[i]][i] = 0;
}
p[i] = u;
}
}
}
}
int main() {
scanf("%d%d", &n, &m);
REP (i, 1, n + 1) {
REP (j, 1, n + 1) {
g[i][j] = LINF;
sg[i][j] = LINF;
rdist[i][j] = LINF;
}
g[i][i] = 0;
sg[i][i] = 0;
}
REP (i, 0, m) {
scanf("%d%d%d%d", &u[i], &v[i], &c[i], &d[i]);
if (c[i] <= g[u[i]][v[i]]) {
sg[u[i]][v[i]] = g[u[i]][v[i]];
g[u[i]][v[i]] = c[i];
} else {
mnto(sg[u[i]][v[i]], (ll) c[i]);
}
}
REP (i, 1, n + 1) {
REP (j, 1, n + 1) {
rdist[i][j] = g[i][j];
}
}
REP (k, 1, n + 1) {
REP (i, 1, n + 1) {
REP (j, 1, n + 1) {
mnto(rdist[i][j], rdist[i][k] + rdist[k][j]);
}
}
}
dij(1, 1);
dij(n, 1);
ll ans = dist[1][n] + dist[n][1];
int cnt = 0;
REP (i, 0, m) {
ll fi = min(dist[1][n], rdist[1][v[i]] + rdist[u[i]][n] + c[i]),
se = min(dist[n][1], rdist[n][v[i]] + rdist[u[i]][1] + c[i]);
debug("%d %d: %lld %lld\n", u[i], v[i], fi, se);
if (sg[u[i]][v[i]] != g[u[i]][v[i]] && onshot[u[i]][v[i]] &&
g[u[i]][v[i]] == c[i]) {
cnt++;
g[u[i]][v[i]] = sg[u[i]][v[i]];
ll tmp = g[v[i]][u[i]];
mnto(g[v[i]][u[i]], (ll) c[i]);
dij(1);
dij(n);
fi = dist[1][n];
se = dist[n][1];
g[u[i]][v[i]] = c[i];
g[v[i]][u[i]] = tmp;
dij(1);
dij(n);
}
debug("%lld %lld\n", fi, se);
mnto(ans, fi + se + d[i]);
}
assert(cnt <= 2 * n);
if (ans < LINF) {
printf("%lld\n", ans);
} else {
printf("-1\n");
}
return 0;
}
