// ~~ icebear ~~
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
template<class T>
bool minimize(T &a, const T &b) {
if (a > b) return a = b, true;
return false;
}
template<class T>
bool maximize(T &a, const T &b) {
if (a < b) return a = b, true;
return false;
}
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "icebear"
const int MOD = 1e9 + 7;
const int inf = 1e9 + 27092008;
const ll INF = 1e18 + 27092008;
const int N = 1e5 + 5;
int n, m, a[N], b[N], c[N], d[N];
vector<int> G[2][N];
bool in_path[N];
ll dist[2][2][N], tmp[N];
int par[N], edge[N];
void dijkstra(int s, ll dist[N], const vector<int> *G) {
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> Q;
fill(dist, dist + n + 1, INF);
fill(par, par + n + 1, 0);
Q.push(mp(0, s));
dist[s] = 0;
while(!Q.empty()) {
int u; ll du;
tie(du, u) = Q.top(); Q.pop();
if (du != dist[u]) continue;
for(int i : G[u]) {
int v = a[i] ^ b[i] ^ u;
if (minimize(dist[v], dist[u] + c[i])) {
par[v] = u;
edge[v] = i;
Q.push(mp(dist[v], v));
}
}
}
for(int t = n; t; t = par[t]) in_path[edge[t]] = true;
}
ll calcDist(int s, int id, ll dist[N]) {
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> Q;
fill(dist, dist + n + 1, INF);
Q.push(mp(0, s));
dist[s] = 0;
while(!Q.empty()) {
ll du; int u;
tie(du, u) = Q.top(); Q.pop();
if (du != dist[u]) continue;
for(int i : G[0][u]) {
if (id == i) continue;
int v = a[i] ^ b[i] ^ u;
if (minimize(dist[v], dist[u] + c[i]))
Q.push(mp(dist[v], v));
}
int v = b[id];
if (u == a[id] && minimize(dist[v], dist[u] + c[id])) Q.push(mp(dist[v], v));
}
return dist[s == 1 ? n : 1];
}
void init(void) {
cin >> n >> m;
FOR(i, 1, m) {
cin >> a[i] >> b[i] >> c[i] >> d[i];
G[0][a[i]].pb(i);
G[1][b[i]].pb(i);
}
}
void process(void) {
dijkstra(1, dist[0][0], G[0]); dijkstra(n, dist[0][1], G[0]);
dijkstra(n, dist[1][0], G[1]); dijkstra(1, dist[1][1], G[1]);
ll ans = min(INF, dist[0][0][n] + dist[0][1][1]);
FOR(i, 1, m) {
if (in_path[i]) minimize(ans, calcDist(1, i, tmp) + calcDist(n, i, tmp) + d[i]);
else {
int u = a[i], v = b[i];
ll dist1 = min(dist[0][0][n], dist[0][0][v] + dist[1][0][u] + c[i]);
ll dist2 = min(dist[0][1][1], dist[0][1][v] + dist[1][1][u] + c[i]);
minimize(ans, dist1 + dist2 + d[i]);
}
}
cout << (ans == INF ? -1 : ans);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int tc = 1;
// cin >> tc;
while(tc--) {
init();
process();
}
return 0;
}
