#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1E12;
vector<ll> dijkstra(int N, int start, vector<vector<ll>> &adj) {
vector<ll> dist(N, INF);
vector<int> check(N, 0);
dist[start] = 0;
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<>> pq;
for (int rep = 0; rep < N; rep++) {
int cur = -1;
ll totalCost = INF;
for (int i = 0; i < N; i++) {
if (!check[i] && dist[i] < totalCost) {
cur = i;
totalCost = dist[i];
}
}
if (cur == -1) {
break;
}
check[cur] = 1;
for (int nxt = 0; nxt < N; nxt++) {
if (dist[nxt] > dist[cur] + adj[cur][nxt]) {
dist[nxt] = dist[cur] + adj[cur][nxt];
}
}
}
return dist;
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int N, M;
cin >> N >> M;
vector<array<ll, 4>> adj(M);
vector<vector<ll>> adj_mat(N, vector<ll>(N, INF));
vector<vector<ll>> rev_mat(N, vector<ll>(N, INF));
for (auto &[x, y, z, w] : adj) {
cin >> x >> y >> z >> w;
x--; y--;
adj_mat[x][y] = min(adj_mat[x][y], z);
rev_mat[y][x] = min(rev_mat[y][x], z);
}
for (int i = 0; i < N; i++) {
adj_mat[i][i] = rev_mat[i][i] = 0;
}
// dist0 : 0 -> i
// dist1 : N - 1 - > i
// dist2 : i -> 0
// dist3 : i -> N - 1
auto dist0 = dijkstra(N, 0, adj_mat);
auto dist1 = dijkstra(N, N - 1, adj_mat);
auto dist2 = dijkstra(N, 0, rev_mat);
auto dist3 = dijkstra(N, N - 1, rev_mat);
map<array<ll, 3>, int> shortest_path;
int ed = N - 1;
while (1) {
bool changed = 0;
for (int i = 0; i < N; i++) {
if (i == ed) {
continue;
}
if (dist0[i] + adj_mat[i][ed] == dist0[ed]) {
shortest_path[{ i, ed, adj_mat[i][ed] }] = 0;
ed = i;
changed = 1;
break;
}
}
if (!changed) {
break;
}
}
ed = 0;
while (1) {
bool changed = 0;
for (int i = 0; i < N; i++) {
if (i == ed) {
continue;
}
if (dist1[i] + adj_mat[i][ed] == dist1[ed]) {
shortest_path[{ i, ed, adj_mat[i][ed] }] = 0;
ed = i;
changed = 1;
break;
}
}
if (!changed) {
break;
}
}
const ll ML = 1200000005;
ll ans = dist0[N - 1] + dist1[0];
for (int i = 0; i < M; i++) {
auto &[u, v, cst, inv] = adj[i];
if (shortest_path.count({ u, v, cst }) && shortest_path[{ u, v, cst }] == 0) {
shortest_path[{ u, v, cst }] = 1;
swap(u, v);
vector<vector<ll>> new_adj(N, vector<ll>(N, INF));
for (int e = 0; e < M; e++) {
new_adj[adj[e][0]][adj[e][1]] = min(new_adj[adj[e][0]][adj[e][1]], adj[e][2]);
}
for (int i = 0; i < N; i++) {
new_adj[i][i] = 0;
}
auto p = dijkstra(N, 0, new_adj);
auto q = dijkstra(N, N - 1, new_adj);
ans = min(ans, p[N - 1] + q[0] + inv);
swap(u, v);
continue;
}
int c_ = cst + inv;
ans = min(ans, min(dist0[N - 1], dist0[v] + dist3[u] + c_) + min(dist1[v] + dist2[u] + c_, dist1[0]));
}
if (ans >= ML) {
cout << -1 << "\n";
} else {
cout << ans << "\n";
}
return 0;
}
