#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fs first
#define sc second
#define mp make_pair
typedef pair<int, int> pii;
struct EDGE {
int u, v, c, d, is_tree[2], id;
EDGE() {}
};
const int MXN = 205, MXM = 50005, INF = 3000000000000000000;
int n, m, dis1[MXN], dis1_inv[MXN], disn[MXN], disn_inv[MXN], p[MXN], dis[MXN];
vector<int> v[MXN][MXN];
EDGE edge[MXM];
bitset<MXN> b;
inline void DIJKSTRA(int sr, int *dis, int id, int inv) {
b.reset();
fill(dis + 1, dis + n + 1, INF);
fill(p + 1, p + n + 1, 0);
dis[sr] = 0;
for (int $ = 0; $ < n; $++) {
int x = -1;
for (int i = 1; i <= n; i++) {
if (b[i]) continue;
if (x == -1) x = i;
else if (dis[x] > dis[i]) x = i;
}
// if (x == -1) cout << "ERROR" << endl;
// cout << "x: " << x << endl;
b[x] = true;
if (id != -1) edge[p[x]].is_tree[id] = true;
for (int j = 1; j <= n; j++) for (auto i : v[x][j]) {
if (inv) {
if (i > 0) continue;
i *= -1;
} else {
if (i < 0) continue;
}
// if (b[i]) continue;
if (dis[x] + edge[i].c < dis[j]) {
dis[j] = dis[x] + edge[i].c;
p[j] = i;
}
}
}
}
inline int SOLVE_1(int id) {
if (edge[id].is_tree[0]) {
DIJKSTRA(1, dis, -1, false);
return dis[n];
}
return min(dis1[n], dis1[edge[id].u] + edge[id].c + disn_inv[edge[id].v]);
}
inline int SOLVE_n(int id) {
if (edge[id].is_tree[1]) {
DIJKSTRA(n, dis, -1, false);
return dis[1];
}
return min(disn[1], disn[edge[id].u] + edge[id].c + dis1_inv[edge[id].v]);
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> edge[i].u >> edge[i].v >> edge[i].c >> edge[i].d;
edge[i].id = v[edge[i].u][edge[i].v].size();
v[edge[i].u][edge[i].v].push_back(i);
v[edge[i].v][edge[i].u].push_back(-i);
}
DIJKSTRA(1, dis1, 0, false);
DIJKSTRA(1, dis1_inv, -1, true);
DIJKSTRA(n, disn, 1, false);
DIJKSTRA(n, disn_inv, -1, true);
// for (int i = 1; i <= m; i++) cout << edge[i].is_tree[1];
// cout << endl;
// return 0;
int x = dis1[n] + disn[1];
for (int i = 1; i <= m; i++) {
swap(edge[i].u, edge[i].v);
v[edge[i].u][edge[i].v][edge[i].id] *= -1;
v[edge[i].v][edge[i].u][edge[i].id] *= -1;
x = min(x, edge[i].d + SOLVE_1(i) + SOLVE_n(i));
swap(edge[i].u, edge[i].v);
v[edge[i].u][edge[i].v][edge[i].id] *= -1;
v[edge[i].v][edge[i].u][edge[i].id] *= -1;
}
cout << (x >= INF ? -1LL : x) << endl;
return 0;
}
