#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxn = 203;
const ll inf = 1e12;
vector<vector<ll>> adj, rev;
vector<vector<bool>> inpath;
vector<array<int, 2>> edges[mxn][mxn];
int n, m;
vector<int> dijkstra(int src, vector<ll> &dist, vector<vector<ll>> &g) {
dist = vector<ll>(n, inf);
dist[src] = 0;
vector<int> p(n, -1);
vector<bool> vis(n, false);
while(true) {
pair<ll, int> mn = {inf, -1};
for(int i = 0; i < n; i++) if(!vis[i])
mn = min(mn, {dist[i], i});
if(mn.first >= inf)
break;
vis[mn.second] = true;
for(int u = 0; u < n; u++) {
if(g[mn.second][u] >= inf) continue;
ll ndist = mn.first + g[mn.second][u];
if(ndist < dist[u]) {
dist[u] = ndist;
p[u] = mn.second;
}
}
}
return p;
}
void extract(int end, vector<int> p) {
vector<int> path;
path.push_back(end);
while(p[path.back()] > -1)
path.push_back(p[path.back()]);
reverse(path.begin(), path.end());
for(int i = 1; i < (int) path.size(); i++)
inpath[path[i - 1]][path[i]] = true;
}
template<typename T>
void out(vector<T> a) {
for(T x : a)
cout << x << ' ';
cout << endl;
}
signed main() {
std::ios::sync_with_stdio(0);
std::cout.tie(0);
std::cin.tie(0);
cin >> n >> m;
adj = rev = vector<vector<ll>>(n, vector<ll>(n, inf));
inpath = vector<vector<bool>>(n, vector<bool>(n, false));
for(int u, v, c, d, i = 0; i < m; i++) {
cin >> u >> v >> c >> d;
u--, v--;
adj[u][v] = min(adj[u][v], (ll) c);
rev[v][u] = min(rev[v][u], (ll) c);
edges[u][v].push_back({c, d});
}
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
sort(edges[i][j].begin(), edges[i][j].end());
vector<ll> d1, dn, r1, rn;
extract(n - 1, dijkstra(0, d1, adj));
extract(0, dijkstra(n - 1, dn, adj));
dijkstra(0, r1, rev);
dijkstra(n - 1, rn, rev);
//out(d1); out(dn); out(r1); out(rn);
ll ans = d1[n - 1] + dn[0];
for(int u = 0; u < n; u++) {
for(int v = 0; v < n; v++) if(!edges[u][v].empty()) {
if(inpath[u][v]) {
ll uv = adj[u][v], vu = adj[v][u];
adj[u][v] = (edges[u][v].size() > 1 ? edges[u][v][1][0] : inf);
adj[v][u] = edges[u][v][0][0];
vector<ll> nd1, ndn;
dijkstra(0, nd1, adj);
dijkstra(n - 1, ndn, adj);
ll cost = nd1[n - 1] + ndn[0] + edges[u][v][0][1];
ans = min(ans, cost);
adj[u][v] = uv;
adj[v][u] = vu;
}
for(int i = 0 + inpath[u][v]; i < (int) edges[u][v].size(); i++) {
auto [c, d] = edges[u][v][i];
ll c1 = d1[v] + rn[u] + c + d; //1 -> v -> u -> n
ll c2 = dn[v] + r1[u] + c + d; //n -> v -> u -> 1
ans = min({ans, c1 + dn[0], c2 + d1[n - 1], c1 + c2 - d});
}
}
}
cout << (ans >= inf ? -1 : ans) << '\n';
return 0;
}
