#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1000;
const int M = 100000;
const ll INF = 1e18;
int n, m;
vector<pair<int, int>> g[2][N];
ll C[M], D[M];
pair<int, int> edges[M];
vector<vector<ll>> dist, par;
vector<ll> dijkstra(int s, int b, bool save = 0) {
vector<ll> d(n + 1, INF);
vector<ll> p(n + 1, -1);
d[s] = 0;
bool processed[n + 1] = {};
while(1) {
s = -1;
for(int i = 1; i <= n; i++) {
if(processed[i]) continue;
if(s == -1 || d[s] > d[i])
s = i;
}
if(s == -1) break;
processed[s] = 1;
for(auto [to, i] : g[b][s]) {
if(d[to] > d[s] + C[i]) {
p[to] = i;
d[to] = d[s] + C[i];
}
}
}
if(save) {
dist.push_back(d);
par.push_back(p);
}
return d;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
edges[i] = {u, v};
cin >> C[i] >> D[i];
g[0][u].push_back({v, i});
g[1][v].push_back({u, i});
}
dijkstra(1, 0, 1);
dijkstra(n, 0, 1);
dijkstra(1, 1, 1);
dijkstra(n, 1, 1);
int cur = n;
set<int> way1, way2;
while(par[0][cur] != -1) {
way1.insert(par[0][cur]);
cur = edges[par[0][cur]].first;
}
if(cur != 1) way1.clear();
cur = 1;
while(par[1][cur] != -1) {
way2.insert(par[1][cur]);
cur = edges[par[1][cur]].first;
}
if(cur != n) way2.clear();
ll res = dist[0][n] + dist[1][1];
for(int i = 0; i < m; i++) {
ll ans = INF;
auto [u, v] = edges[i];
if(!way1.count(i) && !way2.count(i)) {
ans = min(ans, dist[1][v] + dist[2][u] + dist[0][n] + C[i] + D[i]);
ans = min(ans, dist[0][v] + dist[3][u] + dist[1][1] + C[i] + D[i]);
ans = min(ans, dist[0][v] + dist[3][u] + dist[1][v] + dist[2][u] + 2 * C[i] + D[i]);
}
else {
g[0][u].erase(find(g[0][u].begin(), g[0][u].end(), make_pair(v, i)));
g[0][v].push_back({u, i});
auto d1 = dijkstra(1, 0), d2 = dijkstra(n, 0);
ans = min(ans, d1[n] + d2[1] + D[i]);
g[0][u].push_back({v, i});
g[0][v].erase(find(g[0][v].begin(), g[0][v].end(), make_pair(u, i)));
}
res = min(res, ans);
}
if(res >= INF) res = -1;
cout << res;
}
