#include<bits/stdc++.h>
typedef long long ll;
#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl '\n'
#define TASK ""
#define N 200005
#define LOG 17
using namespace std;
bool ghuy4g;
const ll inf = 1e16;
struct Canh {
ll u, v, c, w;
} canh[50004];
ll n, m;
vector<pii> adj[2][N];
int d[2][2][205][205];
ll trace[2][2][205][205], ans = inf;
vector<ll> vt[2][2];
ll is[50004][2][2]; // canh do, voi t0, t1 co bi nam tren duong di hay khong
void dij(ll t0, ll t1, ll t2, ll st) {
priority_queue<pii, vector<pii>, greater<pii>> pq;
for (int i = 1; i <= n; i ++) {
d[t0][t1][t2][i] = inf;
}
d[t0][t1][t2][st] = 0;
pq.push({d[t0][t1][t2][st], st});
while (pq.size()) {
auto u = pq.top().se;
auto c = pq.top().fi;
pq.pop();
if (c > d[t0][t1][t2][u]) continue;
for (auto v : adj[t1][u]) {
if (t2 > 0 && v.se == vt[t0][t1][t2 - 1]) continue;
if (d[t0][t1][t2][v.fi] > c + canh[v.se].c) {
d[t0][t1][t2][v.fi] = c + canh[v.se].c;
trace[t0][t1][t2][v.fi] = v.se;
pq.push({d[t0][t1][t2][v.fi], v.fi});
}
}
}
}
void tv(ll t0, ll t1, ll st) {
/*for (int i = 1; i <= n; i ++) {
if (i == st) continue;
ll id = trace[t0][t1][0][i];
vt[t0][t1].push_back(id);
is[id][t0][t1] = vt[t0][t1].size();
dij(t0, t1, vt[t0][t1].size(), st);
}*/
for (int i = 1; i <= n; i ++) {
if (i == st) continue;
ll id = trace[t0][t1][0][i];
ll u = canh[id].u, v = canh[id].v, c = canh[id].c;
if (t1 == 0) {
if (t0 == 0) {
if (d[0][0][0][u] + c + d[1][1][0][v] != d[0][0][0][n]) {
continue;
}
}
else {
if (d[1][0][0][u] + c + d[0][1][0][v] != d[1][0][0][1]) {
continue;
}
}
}
else if (t1 == 1) {
if (t0 == 0) {
if (d[0][0][0][v] + c + d[1][1][0][u] != d[0][0][0][n]) {
continue;
}
}
else {
if (d[1][0][0][v] + c + d[0][1][0][u] != d[1][0][0][1]) {
continue;
}
}
}
vt[t0][t1].push_back(id);
is[id][t0][t1] = vt[t0][t1].size();
dij(t0, t1, vt[t0][t1].size(), st);
}
}
void pre() {
dij(0, 0, 0, 1); // tu 1
dij(1, 0, 0, n); // tu n
dij(0, 1, 0, 1); // den 1
dij(1, 1, 0, n); // den n
tv(0, 0, 1);
tv(1, 0, n);
tv(0, 1, 1);
tv(1, 1, n);
}
void solve() {
ans = min(ans, d[0][0][0][n] + d[1][0][0][1]);
//cout << ans << endl;
for (int i = 1; i <= m; i ++) {
ll u = canh[i].u, v = canh[i].v, e = canh[i].w + canh[i].c;
// chieu di dis1 = d1 + e + d2;
ll d1 = d[0][0][is[i][0][0]][v];
ll d2 = d[1][1][is[i][1][1]][u];
ll dis1 = min(d[0][0][is[i][0][0]][n], d1 + e + d2);
ll go_not = d[0][0][is[i][0][0]][n];
ll go_use = d1 + d2 + canh[i].c;
// chieu ve dis2 = d1 + e + d2;
d1 = d[1][0][is[i][1][0]][v];
d2 = d[0][1][is[i][0][1]][u];
ll dis2 = min(d[1][0][is[i][1][0]][1], d1 + d2 + e);
ll back_not = d[1][0][is[i][1][0]][1];
ll back_use = d1 + d2 + canh[i].c;
ans = min(ans, canh[i].w + min(go_not, go_use) + min(back_not, back_use));
}
if (ans >= inf) ans = -1;
cout << ans;
}
bool klinh;
signed main() {
// freopen("test.inp", "r", stdin);
//freopen("test.out", "w", stdout);
//srand(time(0));
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i ++) {
ll u, v, c, w;
cin >> u >> v >> c >> w;
adj[0][u].push_back({v, i});
adj[1][v].push_back({u, i});
canh[i] = {u, v, c, w};
}
pre();
solve();
cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
}
