#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 = INTMAX_MAX;
const bool tc = false;
struct edge {
int u, v, c, d;
};
int n, m;
const int mxn = 201;
multiset<pii> adj[mxn]; vector<edge> e;
map<pair<pii, int>, int> id;
void rev() {
for (auto &x : e) {
adj[x.u].erase(adj[x.u].find(mp(x.v, x.c)));
adj[x.v].insert({x.u, x.c});
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);
}
void dijk(int s, vi &d, vector<pii> &p) {
d.assign(n, 1e18);
p.assign(n, {-1, -1});
set<pii> q;
d[s] = 0;
q.insert({0, s});
while (!q.empty()) {
auto cur = *q.begin();
q.erase(q.begin());
int dist = cur.fi;
int u = cur.se;
if (dist != d[u]) continue;
for (auto &neighbour : adj[u]) {
int v = neighbour.fi;
int w = neighbour.se;
if (dist + w < d[v]) {
q.erase({d[v], v});
d[v] = dist + w;
q.insert({d[v], v});
p[v] = {u, w};
}
}
}
}
int solve2() {
// swap an edge from 1 -> n
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 = 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 (auto &x : intree) cout << x;
// cout << '\n';
for (int i = 0; i < m; i++) {
if (intree[i]) {
// bruh
adj[e[i].u].erase(adj[e[i].u].find({e[i].v, e[i].c}));
adj[e[i].v].insert({e[i].u, e[i].c});
vi d1, d2; vector<pii> p1, p2;
dijk(0, d1, p1); dijk(n - 1, d2, p2);
ans = min(ans, d1[n - 1] + d2[0] + e[i].d);
adj[e[i].v].erase(adj[e[i].v].find({e[i].u, e[i].c}));
adj[e[i].u].insert({e[i].v, e[i].c});
} else {
// easy
ans = min(ans, e[i].d + min(df1[n - 1], df1[e[i].v] + e[i].c + dtn[e[i].u]) + dfn[e[i].v] + e[i].c + dt1[e[i].u]);
}
}
return ans;
}
inline void solve() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, c, d;
cin >> u >> v >> c >> d;
u--; v--;
adj[u].insert({v, c});
e.pb({u, v, c, d});
id[mp(mp(u, v), c)] = i;
}
int ans = solve2(); rev(); ans = min(ans, solve2());
cout << (ans >= 1e18 ? -1 : ans) << '\n';
}
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
signed main() {
ios::sync_with_stdio(false);
cout.tie(0);
cin.tie(0);
//setIO();
int t = 1;
if (tc) {
cin >> t;
}
while (t--) {
solve();
}
}
