// Author: caption_mingle
#include "bits/stdc++.h"
using namespace std;
#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define ll long long
const int mod = 1e9 + 7;
const int inf = 2e9;
const int N = 205;
const int M = 50005;
int n, m, d[5][N], p[N];
pair<int, int> trace[N];
bool mark[M];
struct edge {
int u, v, c, d;
} ed[M];
vector<pair<int, int>> g[2][N];
void dijkstra(int id, int st) {
for(int i = 1; i <= n; i++) p[i] = 0, d[id][i] = inf;
d[id][st] = 0;
d[id][0] = inf;
trace[st] = {0, 0};
int eid = (id >> 1) & 1;
for(int i = 1; i <= n; i++) {
int u = 0;
for(int j = 1; j <= n; j++) {
if(!p[j] && d[id][j] < d[id][u]) {
u = j;
}
}
p[u] = 1;
if(d[id][u] >= inf) break;
for(auto [v, x] : g[eid][u]) {
if(d[id][v] > d[id][u] + ed[x].c) {
d[id][v] = d[id][u] + ed[x].c;
trace[v] = {x, u};
}
}
}
int en = st == 1 ? n : 1;
while(en) {
mark[trace[en].fi] = 1;
en = trace[en].se;
}
}
int calc_dist(int st, int en) {
vector<int> dist(n + 1, inf);
for(int i = 1; i <= n; i++) p[i] = 0;
dist[st] = 0;
for(int i = 1; i <= n; i++) {
int u = 0;
for(int j = 1; j <= n; j++) {
if(!p[j] && dist[j] < dist[u]) {
u = j;
}
}
p[u] = 1;
if(dist[u] >= inf) break;
for(auto [v, x] : g[0][u]) {
if(dist[v] > dist[u] + ed[x].c) {
dist[v] = dist[u] + ed[x].c;
}
}
}
return dist[en];
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
#define task ""
if(fopen(task ".INP", "r")) {
freopen(task ".INP", "r", stdin);
freopen(task ".OUT", "w", stdout);
}
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int u, v, c, d; cin >> u >> v >> c >> d;
ed[i] = {u, v, c, d};
g[0][u].pb({v, i});
g[1][v].pb({u, i});
}
dijkstra(0, 1);
dijkstra(1, n);
dijkstra(2, 1);
dijkstra(3, n);
ll ans = 1ll * d[0][n] + d[1][1];
for(int i = 1; i <= m; i++) {
int u = ed[i].u, v = ed[i].v, c = ed[i].c, dd = ed[i].d;
// cerr << i << ' ' << mark[i] << ' ';
if(1) {
g[0][u].erase(find(all(g[0][u]), make_pair(v, i)));
g[0][v].pb({u, i});
ans = min(ans, 1ll * calc_dist(1, n) + 1ll * calc_dist(n, 1) + dd);
g[0][u].pb({v, i});
g[0][v].pop_back();
// cerr << 1ll * calc_dist(1, n) + calc_dist(n, 1) + dd;
} else {
ll d1n = min(d[0][n], d[0][v] + d[3][u] + c);
ll dn1 = min(d[1][1], d[1][v] + d[2][u] + c);
ans = min(ans, d1n + dn1 + dd);
// cerr << d1n + dn1 + dd;
}
// cerr << ln;
}
if(ans >= inf) ans = -1;
cout << ans << ln;
cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC;
}
