#pragma GCC optimize("O3")
#pragma GCC optimize("Os")
#include <iostream>
#include<set>
#include<vector>
const int inf = 2e9;
using namespace std;
vector<vector<int>> g[205], edg;
int d[205][205];
bool p1[50005] = { 0 }, pn[50005] = { 0 };
set<pair<int, int>> q;
int dist[205];
vector<int> ans;
int n, m;
pair<int, int> f, cur;
pair<int, int> prv[205];
void apsp(int n) {
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if((d[i][k] != inf) && (d[k][j] != inf))
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
vector<int> path(int s, int t) {
for (int i = 1; i <= n; ++i) dist[i] = inf;
ans.clear();
for (int i = 1; i <= n; ++i) prv[i] = { -1, -1 };
q.insert({ 0, s }), dist[s] = 0;
while (q.size()) {
f = *q.begin();
q.erase(q.begin());
if (f.second == t) {
q.clear();
break;
}
for (auto y : g[f.second]) {
int i = y[0], x = y[1];
if (dist[i] > (x + f.first)) {
if (dist[i] != inf) q.erase({ dist[i], i });
dist[i] = (x + f.first);
q.insert({ dist[i], i });
prv[i] = { f.second, y[3] };
}
}
}
cur = prv[t];
while (cur.first != -1)
ans.push_back(cur.second), cur = prv[cur.first];
return ans;
}
int excl(int s, int t, int e) {
for (int i = 1; i <= n; ++i) dist[i] = inf;
q.insert({ 0, s }), dist[s] = 0;
while (q.size()) {
f = *q.begin();
q.erase(q.begin());
if (f.second == t) {
q.clear();
return f.first;
}
for (auto y : g[f.second]) {
if (y[3] == e) continue;
int i = y[0], x = y[1];
if (dist[i] > (x + f.first)) {
if (dist[i] != inf) q.erase({ dist[i], i });
dist[i] = (x + f.first);
q.insert({ dist[i], i });
}
}
}
return inf;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
d[i][j] = inf;
for (int i = 1; i <= n; ++i) d[i][i] = 0;
for (int i = 0; i < m; ++i) {
int u, v, c, di; cin >> u >> v >> c >> di;
g[u].push_back({ v, c, di, i });
edg.push_back({ u, v, c, di, i });
d[u][v] = min(d[u][v], c);
}
apsp(n);
if (d[1][n] != inf) {
vector<int> pth = path(1, n);
for (auto x : pth) p1[x] = 1;
}
if (d[n][1] != inf) {
vector<int> pth = path(n, 1);
for (auto x : pth) pn[x] = 1;
}
int ans;
if (max(d[1][n], d[n][1]) >= inf) ans = inf;
else ans = d[1][n] + d[n][1];
for (auto x : edg) {
int c1, c2;
if (!p1[x[4]]) {
int val;
if (max(d[1][x[1]], d[x[0]][n]) >= inf) val = inf;
else val = d[1][x[1]] + x[2] + d[x[0]][n];
c1 = min(d[1][n], val);
}
else {
g[x[1]].push_back({ x[0], x[2], x[3], inf });
c1 = excl(1, n, x[4]);
g[x[1]].pop_back();
}
if (!pn[x[4]]) {
int val;
if (max(d[n][x[1]], d[x[0]][1]) >= inf) val = inf;
else val = d[n][x[1]] + x[2] + d[x[0]][1];
c2 = min(d[n][1], val);
}
else {
g[x[1]].push_back({ x[0], x[2], x[3], inf });
c2 = excl(n, 1, x[4]);
g[x[1]].pop_back();
}
if(max(c1, c2) < inf)
ans = min(ans, c1 + c2 + x[3]);
}
cout << ((ans >= inf) ? -1 : ans);
}
