#include <bits/stdc++.h>
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 4e16;
const int OO = 0;
const int OOO = 1;
using namespace std;
struct edge {
int v, w, i;
edge() {}
edge(int vv, int ww, int ii) {
v = vv;
w = ww;
i = ii;
}
bool operator < (const edge &a) const {
return w > a.w;
}
};
int n, m;
vector<pair<int, int>> e;
vector<int> c, d;
vector<vector<edge>> g;
vector<ll> cost;
vector<int> dist, to;
vector<int> path1, path2;
vector<int> P1, P2; // P1[i] == j if edge i is used as the jth edge (1-indexed), 0 otherwise
// floyd warshall; normal, without p1, without p2
int fw[202][202], fwp1[202][202], fwp2[202][202];
vector<int> dijkstra(int s, int t) {
for (auto &i : dist)
i = -1;
priority_queue<edge> q;
q.push(edge(s, 0, -1));
while (q.size()) {
edge x = q.top();
q.pop();
if (dist[x.v] != -1) continue;
dist[x.v] = x.w;
to[x.v] = x.i;
for (const auto &i : g[x.v])
if (dist[i.v] == -1)
q.push(edge(i.v, x.w + i.w, i.i));
}
if (dist[t] == -1) return{};
vector<int> res;
int cur = t;
while (cur != s) {
res.push_back(to[cur]);
cur = e[to[cur]].first;
}
reverse(res.begin(), res.end());
return res;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
e.resize(m), c.resize(m), d.resize(m);
g.resize(n);
cost.resize(m, 0);
dist.resize(n), to.resize(n);
P1.resize(m, 0), P2.resize(m, 0);
for (int i = 0; i < m; i++) {
cin >> e[i].first >> e[i].second >> c[i] >> d[i];
e[i].first--, e[i].second--;
g[e[i].first].push_back(edge(e[i].second, c[i], i));
}
path1 = dijkstra(0, n - 1), path2 = dijkstra(n - 1, 0);
for (int i = 0; i < path1.size(); i++)
P1[path1[i]] = i + 1;
for (int i = 0; i < path2.size(); i++)
P2[path2[i]] = i + 1;
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
if (i != j)
fw[i][j] = fwp1[i][j] = fwp2[i][j] = md;
else
fw[i][j] = fwp1[i][j] = fwp2[i][j] = 0;
}
for (int i = 0; i < m; i++) {
fw[e[i].first][e[i].second] = min(fw[e[i].first][e[i].second], c[i]);
if (!P1[i])
fwp1[e[i].first][e[i].second] = min(fwp1[e[i].first][e[i].second], c[i]);
if (!P2[i])
fwp2[e[i].first][e[i].second] = min(fwp2[e[i].first][e[i].second], c[i]);
}
for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
fw[i][j] = min(fw[i][j], fw[i][k] + fw[k][j]);
fwp1[i][j] = min(fwp1[i][j], fwp1[i][k] + fwp1[k][j]);
fwp2[i][j] = min(fwp2[i][j], fwp2[i][k] + fwp2[k][j]);
}
if (OO) {
cout << "fw\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) cout << fw[i][j] << " "; cout << '\n';
}
cout << "fwp1\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) cout << fwp1[i][j] << " "; cout << '\n';
}
cout << "fwp2\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) cout << fwp2[i][j] << " "; cout << '\n';
}
cout << "path1:\n";
for (const auto &i : path1) cout << i << " "; cout << '\n';
cout << "path2:\n";
for (const auto &i : path2) cout << i << " "; cout << '\n';
}
// costs for path 1
for (int i = 0; i < m; i++) {
int u = e[i].first, v = e[i].second;
if (!P1[i]) {
if (fw[0][v] == md || fw[u][n - 1] == md) {
if (fw[0][n - 1] == md)
cost[i] += inf;
else
cost[i] += fw[0][n - 1];
}
else if (fw[0][n - 1] == md)
cost[i] += fw[0][v] + c[i] + fw[u][n - 1];
else
cost[i] += min(fw[0][n - 1], fw[0][v] + c[i] + fw[u][n - 1]);
}
else {
int best = md;
for (int l = 0; l < P1[i]; l++) for (int r = P1[i]; r <= path1.size(); r++) {
u = e[path1[l]].first, v = e[path1[r - 1]].second;
if (fw[0][u] != md && fwp1[u][v] != md && fw[v][n - 1] != md)
best = min(best, fw[0][u] + fwp1[u][v] + fw[v][n - 1]);
}
if (best == md)
cost[i] += inf;
else
cost[i] += best;
}
}
// same thing for path 2
for (int i = 0; i < m; i++) {
int u = e[i].first, v = e[i].second;
if (!P2[i]) {
if (fw[n - 1][v] == md || fw[u][0] == md) {
if (fw[n - 1][0] == md)
cost[i] += inf;
else
cost[i] += fw[n - 1][0];
}
else if (fw[n - 1][0] == md)
cost[i] += fw[n - 1][v] + c[i] + fw[u][0];
else
cost[i] += min(fw[n - 1][0], fw[n - 1][v] + c[i] + fw[u][0]);
}
else {
int best = md;
for (int l = 0; l < P2[i]; l++) for (int r = P2[i]; r <= path2.size(); r++) {
u = e[path2[l]].first, v = e[path2[r - 1]].second;
if (fw[n - 1][u] != md && fwp2[u][v] != md && fw[v][0] != md)
best = min(best, fw[n - 1][u] + fwp2[u][v] + fw[v][0]);
}
if (best == md)
cost[i] += inf;
else
cost[i] += best;
}
}
ll ans = inf;
if (fw[0][n - 1] != md && fw[n - 1][0] != md)
ans = min(ans, (ll)fw[0][n - 1] + fw[n - 1][0]);
for (int i = 0; i < m; i++)
ans = min(ans, cost[i] + d[i]);
if (ans > 2 * md)
cout << "-1\n";
else
cout << ans << '\n';
}
