#include <bits/stdc++.h>
#pragma GCC optimize("-O3")
#pragma GCC optimize("-Ofast")
#pragma GCC optimize("unroll-loops")
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
const int inf = 2e9;
vector<ll> D(int x, vector<vector<array<int, 3> > > &v, vector<bool> &u, int ub = 0, int bl = 0) {
int n = sz(v) - 1;
vector<ll> d(n + 1, -1);
vector<int> prv(n + 1);
vector<int> pre(n + 1);
d[x] = 0;
set<array<int, 2> > s;
s.insert({0, x});
while(sz(s)) {
int y = (*s.begin())[1];
s.erase(s.begin());
for(array<int, 3> z : v[y]) {
if(z[2] == bl) continue;
if(d[z[0]] == -1 || d[z[0]] > d[y] + z[1]) {
if(d[z[0]] != -1) { s.erase(s.find({(int)d[z[0]], z[0]})); }
d[z[0]] = d[y] + z[1];
prv[z[0]] = y;
pre[z[0]] = z[2];
s.insert({(int)d[z[0]], z[0]});
}
}
}
if(ub) {
while(prv[ub]) {
u[pre[ub]] = 1;
ub = prv[ub];
}
}
for(ll &x : d) {
if(x == -1) x = inf;
}
return d;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
#ifdef x
freopen("x.txt", "r", stdin);
#endif
int n, m;
cin >> n >> m;
vector<vector<array<int, 3> > > v(n + 1);
vector<vector<array<int, 3> > > u(n + 1);
array<int, 4> x[m + 1];
for(int i = 1; i <= m; ++i) {
for(int j = 0; j < 4; ++j) {
cin >> x[i][j];
}
v[x[i][0]].push_back({x[i][1], x[i][2], i});
u[x[i][1]].push_back({x[i][0], x[i][2], i});
}
vector<bool> rlt(m + 1);
vector<ll> fro = D(1, v, rlt, n);
vector<ll> frn = D(n, v, rlt, 1);
vector<ll> too = D(1, u, rlt);
vector<ll> ton = D(n, u, rlt);
ll fp = fro[n] + frn[1];
for(int i = 1; i <= m; ++i) {
ll tp = 0;
if(rlt[i]) {
v[x[i][1]].push_back({x[i][0], x[i][2], x[i][3]});
tp = x[i][3] + D(1, v, rlt, 0, i)[n] + D(n, v, rlt, 0, i)[1];
v[x[i][1]].pop_back();
} else {
tp = x[i][3]
+ min(fro[n], fro[x[i][1]] + x[i][2] + ton[x[i][0]])
+ min(frn[1], frn[x[i][1]] + x[i][2] + too[x[i][0]]);
}
fp = min(fp, tp);
}
if(fp >= inf) fp = -1;
cout << fp << endl;
return 0;
}
