#include <bits/stdc++.h>
#define LL long long
#define LD long double
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)
using namespace std;
const int nax = 50005;
const LL INF = 1e18;
int n, m;
int e[nax], f[nax], c[nax], d[nax];
bool na[nax];
multiset <pair<LL, int>> s[210][210];
LL cost[210][210];
pair <LL, int> dp[210][210];
LL dp2[210][210];
vector <int> path;
vector <int> ind;
void add(int x) {
if (ss(path) && path.back() == x) return;
path.pb(x);
}
void gao(int a, int b) {
assert(a != b);
if (dp[a][b].fi == cost[a][b]) {
add(a);
add(b);
return;
}
gao(a, dp[a][b].se);
gao(dp[a][b].se, b);
}
LL out[nax];
LL in[nax];
LL fe;
void solve(int skad, int dokad) {
rep(i, 1, n) rep(j, 1, n) {
s[i][j].clear();
cost[i][j] = INF;
}
rep(i, 1, m) {
s[e[i]][f[i]].insert({c[i], i});
cost[e[i]][f[i]] = min(cost[e[i]][f[i]], (LL) c[i]);
na[i] = 0;
in[i] = INF;
}
rep(i, 1, n)
rep(j, 1, n) {
if (i == j) dp[i][j] = {0LL, 0};
else if (!s[i][j].empty()) dp[i][j] = {s[i][j].begin()->fi, 0};
else dp[i][j] = {INF, 0};
}
rep(k, 1, n) rep(i, 1, n) rep(j, 1, n)
dp[i][j] = min(dp[i][j], {dp[i][k].fi + dp[k][j].fi, k});
fe += dp[skad][dokad].fi;
path.clear();
ind.clear();
if (dp[skad][dokad].fi != INF) {
gao(skad, dokad);
}
for (int i = 0; i + 1 < ss(path); ++i) {
int a = path[i];
int b = path[i + 1];
int id = s[a][b].begin()->se;
s[a][b].erase(s[a][b].begin());
na[id] = 1;
ind.pb(id);
}
rep(i, 1, n) rep(j, 1, n) {
if (i == j) dp2[i][j] = 0LL;
else if(ss(s[i][j])) dp2[i][j] = s[i][j].begin()->fi;
else dp2[i][j] = INF;
}
rep(k, 1, n) rep(i, 1, n) rep(j, 1, n)
dp2[i][j] = min(dp2[i][j], dp2[i][k] + dp2[k][j]);
rep(i, 1, m) {
if (!na[i]) {
out[i] += min(dp[skad][dokad].fi, c[i] + dp[skad][f[i]].fi + dp[e[i]][dokad].fi);
}
}
for (int i = 0; i < ss(path); ++i)
for (int j = i + 1; j < ss(path); ++j) {
int a = path[i];
int b = path[j];
LL val = dp2[a][b] + dp[skad][a].fi + dp[b][dokad].fi;
for (int k = i; k < j; ++k)
in[ind[k]] = min(in[ind[k]], val);
}
rep(i, 1, m)
if (na[i])
out[i] += in[i];
}
int main() {
scanf ("%d%d", &n, &m);
rep(i, 1, m) {
scanf ("%d%d%d%d", e + i, f + i, c + i, d + i);
}
solve(1, n);
solve(n, 1);
LL best = fe;
rep(i, 1, m) best = min(best, out[i] + d[i]);
if (best >= INF) printf ("-1\n");
else printf ("%lld", best);
return 0;
}
