#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
vector<multiset<pair<int, int>>> g;
void djikstra(int src, vector<long long> &sp) {
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
pq.push({sp[src] = 0, src});
while (pq.size()) {
int u = pq.top().second;
pq.pop();
for (auto [v, w] : g[u]) {
if (sp[u] + w < sp[v])
sp[v] = sp[u] + w, pq.push({sp[v], v});
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
g.resize(n);
vector<long long> sp1, sp2;
vector<tuple<int, int, int, int>> edges;
for (int i = 0; i < m; i++) {
int u, v, c, d;
cin >> u >> v >> c >> d;
--u, --v;
g[u].insert({v, c});
edges.push_back({u, v, c, d});
}
sp1 = sp2 = vector<long long> (n, INF);
djikstra(0, sp1), djikstra(n - 1, sp2);
long long ans = min(INF, sp1[n - 1] + sp2[0]);
for (auto [u, v, c, d] : edges) {
g[u].erase(g[u].find({v, c}));
g[v].insert({u, c});
sp1 = sp2 = vector<long long> (n, INF);
djikstra(0, sp1), djikstra(n - 1, sp2);
ans = min(ans, sp1[n - 1] + sp2[0] + d);
g[v].erase(g[v].find({u, c}));
g[u].insert({v, c});
}
cout << (ans == INF ? -1 : ans) << '\n';
}
