#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second
const ll N = 200 + 5, inf = 1e18, mod = 1e9 + 7, block = 320, lim = 16;
int n, m;
struct item {
int v, c, d, id;
};
struct node {
int u, v, c, d;
} a[100005];
vector <item> adj[N], adj1[N];
pii edge[N][N];
int length[N];
bool check[100005], check1[100005];
int road1[100005], road2[100005];
int dist[N][N];
void dijk(int u, vector <pii> &trace, int cant) {
for (int i = 1; i <= n; i++) {
length[i] = inf;
trace[i] = make_pair(0, 0);
}
length[u] = 0;
priority_queue <pii, vector <pii>, greater <pii> > q;
q.push({0, u});
while(q.size()) {
auto [val, u] = q.top();
q.pop();
// cout << u << ' ' << val << '\n';
if (val > length[u]) continue;
for (auto [v, c, d, id] : adj[u]) {
if (id == cant) continue;
// cout << v << ' ' << length[v] << '\n';
if (length[v] > length[u] + c) {
// cout << u << ' ' << v << ' ';
length[v] = length[u] + c;
trace[v] = {u, id};
q.push({length[v], v});
}
}
}
}
void floyd() {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
if (fopen(".inp", "r")) {
freopen(".inp", "r", stdin);
freopen(".out", "w", stdout);
}
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) if (i != j) dist[i][j] = inf;
}
for (int i = 1; i <= m; i++) {
int u, v, c, d;
cin >> u >> v >> c >> d;
a[i] = {u, v, c, d};
adj[u].push_back({v, c, d, i});
dist[u][v] = min(dist[u][v], c);
}
floyd();
vector <pii> trace1(n + 1, make_pair(0, 0));
// cout << 1 << flush;
dijk(1, trace1, -1);
int minn = length[n];
int t = n;
while(t > 0) {
// cout << t << ' ';
auto [v, id] = trace1[t];
if (v == 0) break;
check[id] = true;
t = v;
}
for (int i = 1; i <= m; i++) {
if (check[i]) {
dijk(1, trace1, i);
road1[i] = length[n];
}
else road1[i] = minn;
}
dijk(n, trace1, -1);
int minn2 = length[1];
t = 1;
while(t > 0) {
// cout << t << ' ';
auto [v, id] = trace1[t];
if (v == 0) break;
check1[id] = true;
t = v;
}
// cout << minn << ' ' << minn2 << '\n';
for (int i = 1; i <= m; i++) {
if (check1[i]) {
dijk(n, trace1, i);
// cout << "ch: " << i << ' ' << length[1] << '\n';
road2[i] = length[1];
}
else road2[i] = minn2;
}
// cout << dist[1][3] << '\n';
// for (int i = 1; i <= m; i++) cout << road1[i] << ' ' << road2[i] << '\n';
// cout << "ok: ";
// for (int i = 1; i <= m; i++) cout << check[i] << ' ';
int ans = inf;
if (dist[1][n] < inf && dist[n][1] < inf) ans = min(ans, dist[1][n] + dist[n][1]);
for (int i = 1; i <= m; i++) {
if (road1[i] < inf && road2[i] < inf) ans = min(ans, road1[i] + road2[i]);
}
for (int i = 1; i <= m; i++) {
int u = a[i].u, v = a[i].v, c = a[i].c, d = a[i].d;
int val1 = inf, val2 = inf;
if (dist[1][v] < inf && dist[u][n] < inf) val1 = dist[1][v] + c + dist[u][n];
if (dist[n][v] < inf && dist[u][1] < inf) val2 = dist[n][v] + c + dist[u][1];
if (val1 < inf && dist[n][1] < inf) ans = min(ans, (val1 + road2[i] + d));
if (val2 < inf && dist[1][n] < inf) ans = min(ans, (road1[i] + val2 + d));
}
if (ans >= inf) cout << -1;
else cout << ans;
return 0;
}
