#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], radj[N];
bool check[100005], check1[100005];
int road1[100005], road2[100005];
int lenArr[N];
void dijk_forbid(int src, int cant, vector<item> graph[], int out[]) {
for (int i = 1; i <= n; i++) out[i] = inf;
out[src] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
q.push({0, src});
while (!q.empty()) {
auto t = q.top(); q.pop();
int val = t.fi, u = t.se;
if (val > out[u]) continue;
for (auto it : graph[u]) {
int v = it.v, c = it.c, id = it.id;
if (id == cant) continue;
if (out[v] > out[u] + c) {
out[v] = out[u] + c;
q.push({out[v], v});
}
}
}
}
void dijk_no_forbid(int src, vector<item> graph[], int out[]) {
dijk_forbid(src, -1, graph, out);
}
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 <= 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});
radj[v].push_back({u, c, d, i});
}
static int from1[N], toN[N], fromN[N], to1[N];
dijk_no_forbid(1, adj, from1);
dijk_no_forbid(n, radj, toN);
dijk_no_forbid(n, adj, fromN);
dijk_no_forbid(1, radj, to1);
int ans = inf;
if (from1[n] < inf && fromN[1] < inf) ans = min(ans, from1[n] + fromN[1]);
int minn = from1[n], minn2 = fromN[1];
for (int i = 1; i <= m; i++) {
int u = a[i].u, v = a[i].v, c = a[i].c;
if (from1[u] < inf && toN[v] < inf && from1[u] + c + toN[v] == minn) check[i] = true;
}
for (int i = 1; i <= m; i++) {
if (check[i]) {
dijk_forbid(1, i, adj, lenArr);
road1[i] = lenArr[n];
} else road1[i] = minn;
}
for (int i = 1; i <= m; i++) {
int u = a[i].u, v = a[i].v, c = a[i].c;
if (fromN[u] < inf && to1[v] < inf && fromN[u] + c + to1[v] == minn2) check1[i] = true;
}
for (int i = 1; i <= m; i++) {
if (check1[i]) {
dijk_forbid(n, i, adj, lenArr);
road2[i] = lenArr[1];
} else road2[i] = minn2;
}
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 (from1[u] < inf && toN[v] < inf) val1 = from1[u] + c + toN[v];
if (fromN[u] < inf && to1[v] < inf) val2 = fromN[u] + c + to1[v];
if (val1 < inf && road2[i] < inf) ans = min(ans, val1 + road2[i] + d);
if (val2 < inf && road1[i] < inf) ans = min(ans, road1[i] + val2 + d);
}
if (ans >= inf) cout << -1;
else cout << ans;
return 0;
}
