#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define SZ(x) ((int)((x).size()))
#define debug(x) cerr << #x << " = " << x << '\n'
const int mxn = 205, mxm = 5e4+5;
array<int,4> ed[mxm];
int n,m, ex[mxm];
vector<array<int,3>> adj[mxn], radj[mxn];
struct graph {
ll dis[mxn], vis[mxn], pred[mxn], on[mxm];
void dij(int rev, int s) { //to, cost, idx
for (int q = 0; q < mxn; q++) {
dis[q] = pred[q] = INT_MAX;
vis[q] = 0;
}
for (int q = 0; q < mxm; q++) on[q] = 0;
dis[s] = 0;
for (int q = 0; q < n; q++) {
int v = -1;
for (int w = 1; w <= n; w++) {
if (!vis[w] && (v == -1 || dis[w] < dis[v])) v = w;
}
if (v == -1 || dis[v] == INT_MAX) break;
vis[v] = 1;
if (!rev) {
for (int w = 0; w < SZ(adj[v]); w++) {
if (!ex[adj[v][w][2]]) continue;
if (dis[v]+adj[v][w][1] < dis[adj[v][w][0]]) {
dis[adj[v][w][0]] = dis[v]+adj[v][w][1];
pred[adj[v][w][0]] = adj[v][w][2];
}
}
} else {
for (int w = 0; w < SZ(radj[v]); w++) {
if (!ex[radj[v][w][2]]) continue;
if (dis[v]+radj[v][w][1] < dis[radj[v][w][0]]) {
dis[radj[v][w][0]] = dis[v]+radj[v][w][1];
pred[radj[v][w][0]] = radj[v][w][2];
}
}
}
}
for (int q = 1; q <= n; q++) if (pred[q] != INT_MAX) on[pred[q]] = 1;
}
} g[5];
ll get(int x, int y, int i) {
if (x == 1) {
if (g[0].on[i]) {
g[4].dij(0,1);
return g[4].dis[y];
} else return g[0].dis[y];
} else if (x == n) {
if (g[2].on[i]) {
g[4].dij(0,n);
return g[4].dis[y];
} else return g[2].dis[y];
} else if (y == 1) {
if (g[1].on[i]) {
g[4].dij(1,1);
return g[4].dis[x];
} else return g[1].dis[x];
} else {
if (g[3].on[i]) {
g[4].dij(1,n);
return g[4].dis[x];
} else return g[3].dis[x];
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for (int q = 0; q < m; q++) {
for (int w = 0; w < 4; w++) {
cin >> ed[q][w];
}
ex[q] = 1;
adj[ed[q][0]].push_back({ed[q][1],ed[q][2],q});
radj[ed[q][1]].push_back({ed[q][0],ed[q][2],q});
}
g[0].dij(0,1);
g[1].dij(1,1);
g[2].dij(0,n);
g[3].dij(1,n);
ll ans = INT_MAX;
ans = min(ans, g[0].dis[n]+g[2].dis[1]);
for (int q = 0; q < m; q++) {
ex[q] = 0;
ll a = min(get(1,n,q),get(1,ed[q][1],q)+get(ed[q][0],n,q)+ed[q][2]);
ll b = min(get(n,1,q),get(n,ed[q][1],q)+get(ed[q][0],1,q)+ed[q][2]);
ans = min(ans, a+b+ed[q][3]);
ex[q] = 1;
}
if (ans == INT_MAX) cout << "-1\n";
else cout << ans << '\n';
return 0;
}
