#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;
using ll = long long;
const ll inf = 1e15;
struct Edge {
int v;
ll c;
int id;
};
struct InputEdge {
int u, v;
ll c, d;
};
vector<InputEdge> edges;
vector<vector<Edge>> base_adj;
int n, m;
vector<ll> dijkstra_modified(int start, int remove_id, InputEdge add_edge) {
vector<ll> dist(n+1, inf);
vector<bool> visited(n+1, false);
dist[start] = 0;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
pq.push({0, start});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d != dist[u]) continue;
visited[u] = true;
if (remove_id == -1) {
for (const Edge& e : base_adj[u]) {
ll nd = d + e.c;
if (nd < dist[e.v]) {
dist[e.v] = nd;
pq.push({nd, e.v});
}
}
} else {
if (u == add_edge.u) {
for (const Edge& e : base_adj[u]) {
if (e.id == remove_id) continue;
ll nd = d + e.c;
if (nd < dist[e.v]) {
dist[e.v] = nd;
pq.push({nd, e.v});
}
}
} else if (u == add_edge.v) {
for (const Edge& e : base_adj[u]) {
ll nd = d + e.c;
if (nd < dist[e.v]) {
dist[e.v] = nd;
pq.push({nd, e.v});
}
}
ll nd = d + add_edge.c;
if (nd < dist[add_edge.u]) {
dist[add_edge.u] = nd;
pq.push({nd, add_edge.u});
}
} else {
for (const Edge& e : base_adj[u]) {
ll nd = d + e.c;
if (nd < dist[e.v]) {
dist[e.v] = nd;
pq.push({nd, e.v});
}
}
}
}
}
return dist;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
base_adj.resize(n+1);
edges.resize(m);
for (int i = 0; i < m; i++) {
int u, v;
ll c, d;
cin >> u >> v >> c >> d;
edges[i] = {u, v, c, d};
base_adj[u].push_back({v, c, i});
}
vector<ll> dist_forward0 = dijkstra_modified(1, -1, {0,0,0,0});
vector<ll> dist_backward0 = dijkstra_modified(n, -1, {0,0,0,0});
ll total0 = inf;
if (dist_forward0[n] < inf && dist_backward0[1] < inf) {
total0 = dist_forward0[n] + dist_backward0[1];
}
ll ans = total0;
for (int i = 0; i < m; i++) {
InputEdge e = edges[i];
vector<ll> dist_forward = dijkstra_modified(1, i, e);
vector<ll> dist_backward = dijkstra_modified(n, i, e);
if (dist_forward[n] < inf && dist_backward[1] < inf) {
ll total_i = dist_forward[n] + dist_backward[1] + e.d;
if (total_i < ans) {
ans = total_i;
}
}
}
if (ans >= inf) {
cout << -1 << endl;
} else {
cout << ans << endl;
}
return 0;
}
