#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 24;
const ll INF = 1e18;
struct Edge {
int u, v, c, d;
} E[N];
int n, m;
vector<int> g[2][N];
vector<ll> dist[2][2];
bool mp[N];
void gen_dist(int start, vector<ll> &d, bool rev) {
d.assign(n + 1, INF);
vector<int> vis(n + 1, 0), par(n + 1, 0);
d[start] = 0;
for (int _ = 0; _ < n; _++) {
int u = 0;
for (int i = 1; i <= n; i++) {
if (!vis[i] && (u == 0 || d[u] > d[i])) u = i;
}
vis[u] = 1;
for (int i: g[rev][u]) {
int v = u ^ E[i].u ^ E[i].v, w = E[i].c;
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
par[v] = i;
}
}
}
for (int u = 1; u <= n; u++) {
if (par[u]) mp[par[u]] = 1;
}
}
ll calc_dist(int start, int end) {
vector<ll> d(n + 1, INF);
vector<int> vis(n + 1, 0);
d[start] = 0;
for (int _ = 0; _ < n; _++) {
int u = 0;
for (int i = 1; i <= n; i++) {
if (!vis[i] && (u == 0 || d[u] > d[i])) u = i;
}
vis[u] = 1;
for (int i: g[0][u]) {
int v = u ^ E[i].u ^ E[i].v, w = E[i].c;
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
}
}
}
return d[end];
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
auto &[u, v, c, d] = E[i];
cin >> u >> v >> c >> d;
g[0][u].push_back(i);
g[1][v].push_back(i);
}
gen_dist(1, dist[0][0], 0);
gen_dist(1, dist[0][1], 1);
gen_dist(n, dist[1][0], 0);
gen_dist(n, dist[1][1], 1);
ll res = dist[0][0][n] + dist[1][0][1];
for (int i = 1; i <= m; i++) {
auto &[u, v, c, d] = E[i];
if (!mp[i]) {
ll dist_1n = min(dist[0][0][n], dist[0][0][v] + c + dist[1][1][u]);
ll dist_n1 = min(dist[1][0][1], dist[1][0][v] + c + dist[0][1][u]);
res = min(res, dist_1n + dist_n1 + d);
}
else {
g[0][u].erase(find(g[0][u].begin(), g[0][u].end(), i));
g[0][v].push_back(i);
res = min(res, calc_dist(1, n) + calc_dist(n, 1) + d);
g[0][v].pop_back();
g[0][u].push_back(i);
}
}
if (res >= INF) res = -1;
cout << res << '\n';
}
int main() {
cin.tie(0) -> sync_with_stdio(0);
int T = 1; // cin >> T;
while (T--) {
solve();
}
}
