#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
vector<multiset<pair<int, int> > > adj;
vector<ll> sssp1, sssp2;
void dijkstra(int u, vector<ll>& sssp){
priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq;
pq.push({sssp[u] = 0ll, u});
while(!pq.empty()) {
int x = pq.top().ss;
pq.pop();
for(auto [y, w] : adj[x])
if(sssp[x] + w < sssp[y])
pq.push({sssp[y] = sssp[x] + w, y});
}
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
int n, m; cin >> n >> m;
adj.resize(n);
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--;
adj[u].insert({v, c});
edges.push_back(make_tuple(u, v, c, d));
}
sssp1 = sssp2 = vector<ll>(n, INT_MAX);
dijkstra(0, sssp1);
dijkstra(n - 1, sssp2);
ll ans = min((ll)INT_MAX, sssp1[n - 1] + sssp2[0]);
for(auto [u, v, c, d] : edges){
adj[u].erase(adj[u].find({v, c}));
adj[v].insert({u, c});
sssp1 = sssp2 = vector<ll>(n, INT_MAX);
dijkstra(0, sssp1);
dijkstra(n - 1, sssp2);
ans = min(ans, sssp1[n - 1] + sssp2[0] + d);
adj[v].erase(adj[v].find({u, c}));
adj[u].insert({v, c});
}
cout << (ans == INT_MAX ? -1 : ans) << '\n';
}
