#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define int long long
#define all(x) (x).begin(), (x).end()
typedef long double ld;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef map<int, int> mii;
typedef unordered_map<int, int> umii;
const int mod = 1e9 + 7;
const int inf = (int)4e18;
const bool tc = false;
struct edge {
int u, v, c, d;
};
int n, m;
const int mxn = 201;
vector<pii> adj[mxn];
vector<edge> e;
map<pair<pii, int>, int> id;
void build_adj() {
for (int i = 0; i < n; i++) adj[i].clear();
for (auto &x : e) adj[x.u].pb({x.v, x.c});
}
void rev() {
for (auto &x : e) swap(x.u, x.v);
map<pair<pii, int>, int> id2;
for (auto &[k, val] : id) {
auto [uv, c] = k;
auto [u, v] = uv;
id2[{{v, u}, c}] = val;
}
id = move(id2);
build_adj();
}
void dijk(int s, vi &d, vector<pii> &p) {
d.assign(n, inf);
p.assign(n, {-1, -1});
priority_queue<pii, vector<pii>, greater<pii>> q;
d[s] = 0;
q.push({0, s});
while (!q.empty()) {
auto [dist, u] = q.top();
q.pop();
if (dist != d[u]) continue;
for (auto &neighbour : adj[u]) {
int v = neighbour.fi;
int w = neighbour.se;
if (dist + w < d[v]) {
d[v] = dist + w;
p[v] = {u, w};
q.push({d[v], v});
}
}
}
}
int solve2() {
vector<int> df1, dtn, dt1, dfn;
vector<pii> pf1, ptn, pt1, pfn;
dijk(0, df1, pf1);
dijk(n - 1, dfn, pfn);
rev();
dijk(n - 1, dtn, ptn);
dijk(0, dt1, pt1);
rev();
int ans = inf;
if (df1[n - 1] < inf && dfn[0] < inf) ans = df1[n - 1] + dfn[0];
vi intree(m);
for (int i = 0; i < n; i++) {
if (pf1[i].fi != -1) intree[id[{{pf1[i].fi, i}, pf1[i].se}]] = 1;
if (pfn[i].fi != -1) intree[id[{{pfn[i].fi, i}, pfn[i].se}]] = 1;
if (pt1[i].fi != -1) intree[id[{{i, pt1[i].fi}, pt1[i].se}]] = 1;
if (ptn[i].fi != -1) intree[id[{{i, ptn[i].fi}, ptn[i].se}]] = 1;
}
for (int i = 0; i < m; i++) {
if (intree[i]) {
swap(e[i].u, e[i].v);
build_adj();
vi d1, d2;
vector<pii> p1, p2;
dijk(0, d1, p1);
dijk(n - 1, d2, p2);
if (d1[n - 1] < inf && d2[0] < inf) {
ans = min(ans, d1[n - 1] + d2[0] + e[i].d);
}
swap(e[i].u, e[i].v);
build_adj();
} else {
int a = inf, b = inf;
if (df1[n - 1] < inf) a = min(a, df1[n - 1]);
if (df1[e[i].v] < inf && dtn[e[i].u] < inf) {
a = min(a, df1[e[i].v] + e[i].c + dtn[e[i].u]);
}
if (dfn[0] < inf) b = min(b, dfn[0]);
if (dfn[e[i].v] < inf && dt1[e[i].u] < inf) {
b = min(b, dfn[e[i].v] + e[i].c + dt1[e[i].u]);
}
if (a < inf && b < inf) ans = min(ans, e[i].d + a + b);
}
}
return ans;
}
inline void solve() {
cin >> n >> m;
e.clear();
id.clear();
for (int i = 0; i < n; i++) adj[i].clear();
for (int i = 0; i < m; i++) {
int u, v, c, d;
cin >> u >> v >> c >> d;
u--, v--;
e.pb({u, v, c, d});
id[mp(mp(u, v), c)] = i;
}
build_adj();
int ans = solve2();
rev();
ans = min(ans, solve2());
cout << (ans >= inf / 2 ? -1 : ans) << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cout.tie(0);
cin.tie(0);
int t = 1;
if (tc) cin >> t;
while (t--) solve();
}
