#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii; typedef vector<int> vi;
struct Edge {
int u, v, c, d;
};
int n, m;
vector<multiset<pii>> adj;
int min_dist(int src, int dest){
vi dist(n, -1);
priority_queue<pii, vector<pii>, greater<pii>> pq;
dist[src] = 0;
pq.push({0, src});
while (!pq.empty()){
auto [d, u] = pq.top();
pq.pop();
if (d != dist[u]) continue;
for (auto [v, w] : adj[u]){
if (dist[v] == -1 || (d + w) < dist[v]){
dist[v] = d + w;
if (v != dest)
pq.push({dist[v], v});
}
}
}
return dist[dest];
}
int32_t main(){
cin >> n >> m;
adj.assign(n, multiset<pii>());
vector<Edge> edges(m);
for (auto &[u, v, c, d] : edges){
cin >> u >> v >> c >> d;
u--, v--;
adj[u].insert({v, c});
}
int ans = -1;
int fw = min_dist(0, n-1);
if (fw != -1){
int bw = min_dist(n-1, 0);
if (bw != -1)
ans = fw + bw;
}
for (auto [u, v, c, d] : edges){
adj[u].erase(adj[u].find({v, c}));
adj[v].insert({u, c});
int fw = min_dist(0, n-1), bw;
if (fw == -1)
goto rollback;
bw = min_dist(n-1, 0);
if (bw == -1)
goto rollback;
if (ans == -1 || (fw + d + bw) < ans)
ans = fw + d + bw;
rollback:
adj[v].erase(adj[v].find({u, c}));
adj[u].insert({v, c});
}
cout << ans << endl;
return 0;
}
