#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define int long long
using namespace std;
const int N = 205;
const int M = 5e4 + 5;
const int oo = 1e18;
vector <int> adj[N];
vector <int> newadj[N];
pair <int, int> edge[M];
int dis[N][N];
int d[N];
int f[M];
int g[M];
int par[N];
int cost[M];
int revcost[M];
int n,m;
bool vis[N];
bool flag[M];
bool mark[N];
template <typename T>
bool mini(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
void dfs(int u, int p) {
par[u] = p;
for (int id : newadj[u]) {
int v = edge[id].se;
d[v] = d[u] + 1;
dfs(v, id);
}
}
void solve(int f[], int s, int t) {
for (int i = 1; i <= n; i++) {
vis[i] = mark[i] = false;
newadj[i].clear();
}
for (int i = 1; i <= m; i++)
flag[i] = false;
queue <int> q({s});
vis[s] = true;
while (q.size()) {
int u = q.front();
q.pop();
for (int id : adj[u]) {
int v = edge[id].se;
if (!vis[v] && dis[s][u] + cost[id] == dis[s][v]) {
vis[v] = true;
q.push(v);
newadj[u].push_back(id);
}
}
}
if (!vis[t]) {
for (int i = 1; i <= m; i++)
f[i] = oo;
return;
}
d[s] = 0;
dfs(s, -1);
for (int u = t; u != s; u = edge[par[u]].fi) {
flag[par[u]] = true;
mark[u] = true;
}
mark[s] = true;
for (int i = 1; i <= m; i++)
f[i] = (flag[i]) ? oo : dis[s][t];
for (int i = 1; i <= m; i++) if (!flag[i]) {
int u = edge[i].fi;
int v = edge[i].se;
if (dis[s][u] == oo)
continue;
int res = dis[s][u] + dis[v][t] + cost[i];
while (!mark[u])
u = edge[par[u]].fi;
if (d[v] < d[u])
continue;
if (mark[v]) {
for (; v != u; v = edge[par[v]].fi)
mini(f[par[v]], res);
}
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++)
cin >> edge[i].fi >> edge[i].se >> cost[i] >> revcost[i];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j)
dis[i][j] = oo;
for (int i = 1; i <= m; i++) {
int u = edge[i].fi;
int v = edge[i].se;
mini(dis[u][v], cost[i]);
adj[u].push_back(i);
}
for (int j = 1; j <= n; j++)
for (int i = 1; i <= n; i++)
for (int k = 1; k <= n; k++)
mini(dis[i][k], dis[i][j] + dis[j][k]);
// for (int i = 1; i <= n; i++)
// for (int j = 1; j <= n; j++)
// cerr << i << " " << j << " " << dis[i][j] << "\n"
int ans = 2 * oo;
if (dis[1][n] < oo && dis[n][1] < oo)
ans = min(ans, dis[1][n] + dis[n][1]);
solve(f, 1, n);
solve(g, n, 1);
// for (int i = 1; i <= m; i++)
// cerr << f[i] << " \n"[i == m];
// for (int i = 1; i <= m; i++)
// cerr << g[i] << " \n"[i == m];
for (int i = 1; i <= m; i++) {
int u = edge[i].fi;
int v = edge[i].se;
int l = f[i];
int r = g[i];
if (dis[1][n] > dis[1][v] + dis[u][n] + cost[i])
l = dis[1][v] + dis[u][n] + cost[i];
if (dis[n][1] > dis[n][v] + dis[u][1] + cost[i])
r = dis[n][v] + dis[u][1] + cost[i];
// cerr << i << " " << l << " " << r << "\n";
if (l < oo && r < oo)
ans = min(ans, l + r + revcost[i]);
}
if (ans == 2 * oo)
ans = -1;
cout << ans;
return 0;
}
