#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'
/*
* Mark edges in the shortest-path tree with source as 0 and then n-1.
* Run floyd-warshall.
* ans = dist[0][n-1]
* For each edge (u -> v):
* if it is in any tree:
* run dijkstra from 0 and then from n-1 excluding this edge (newDist)
* ans = min(ans, newDist[0][n-1] + newdist[n-1][v] + w + c + dist[u][0])
* (dist[u][0] can use this edge in its initial direction, but then it would be better
* to go directly from v -> 0 rather than going to u first, and the initial answer would be better itself)
* else:
* ans = min(ans, dist[0][n-1] + dist[n-1][v] + w + c + dist[u][0])
* (again same argument for why dist[u][0] can be used)
*/
int n, m;
vector<vector<vector<ll>>> adj;
const ll INF = 1e15;
void dijk(int s, vi &pre, vector<ll> &dist, int del=-1) {
dist[s] = 0;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
pq.push({0, s});
while (pq.size()) {
int p = pq.top().second; ll d = pq.top().first; pq.pop();
if (dist[p] != d) continue;
for (auto &i: adj[p]) if (i[2] != del and dist[i[0]] > i[1]+d) {
pre[i[0]] = i[2];
dist[i[0]] = i[1]+d;
pq.push({dist[i[0]], i[0]});
}
}
}
int main() {
#ifdef mlocal
freopen("test.in", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
adj.resize(n);
vector<vector<ll>> edges(m);
vector<vector<ll>>dist(n, vector<ll>(n, INF));
for_(i, 0, n) dist[i][i] = 0;
for_(i, 0, m) {
int a, b; ll d, c; cin >> a >> b >> d >> c;
a -= 1; b -= 1;
edges[i] = {a, b, d, c, i};
adj[a].push_back({b, d, i});
dist[a][b] = min(dist[a][b], d);
}
for_(k, 0, n) for_(i, 0, n) for_(j, 0, n) dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
vector<vector<ll>> currDist(2, vector<ll>(n, INF));
vi pre(n, -1);
vector<bool> used(m);
dijk(0, pre, currDist[0]);
for_(i, 0, n) if (pre[i] != -1) used[pre[i]] = true;
pre.assign(n, -1);
dijk(n-1, pre, currDist[1]);
for_(i, 0, n) if (pre[i] != -1) used[pre[i]] = true;
ll ans = dist[0][n-1]+dist[n-1][0];
for_(i, 0, n) assert(dist[0][i] == currDist[0][i] and dist[n-1][i] == currDist[1][i]);
for_(i, 0, m) {
int u = edges[i][0], v = edges[i][1], idx = edges[i][4]; ll d = edges[i][2], c = edges[i][3];
if (used[idx]) {
currDist.assign(2, vector<ll>(n, INF));
dijk(0, pre, currDist[0], i);
dijk(n-1, pre, currDist[1], i);
ans = min(ans, currDist[0][n-1] + currDist[1][v] + d + c + dist[u][0]);
} else ans = min(ans, dist[0][n-1] + dist[n-1][v] + d + c + dist[u][0]);
}
cout << (ans >= INF ? -1 : ans) << endl;
return 0;
}
