#include <bits/stdc++.h>
using namespace std;
const int N = 201, M = 50000;
int dist[N][N], depth[N], prv[N], n, m;
bool path_1[M], path_n[M], path[M];
vector<array<int, 3>> adj[N];
array<int, 4> edges[M];
int dijkstra(int s, int t, bool *path) {
fill(adj, adj + n + 1, vector<array<int, 3>>());
fill(depth, depth + n + 1, INT_MAX);
for (int j = 0; j < m; ++j) {
auto [u, v, c, d] = edges[j];
adj[u].push_back({v, c, j});
}
priority_queue<array<int, 2>> queue;
queue.push({0, s});
depth[0] = 0;
while (!queue.empty()) {
auto [d, u] = queue.top();
queue.pop();
d = -d;
if (d > depth[u]) {
continue;
}
for (auto [c, w, i] : adj[u]) {
if (d + w < depth[c]) {
prv[c] = i;
depth[c] = d + w;
queue.push({-depth[c], c});
}
}
}
if (depth[t] < INT_MAX) {
int i = t;
while (i != s) {
auto [u, v, c, d] = edges[prv[i]];
path[prv[i]] = true;
i = u;
}
}
return depth[t];
}
int calc(int s, int t, int i) {
auto [u, v, c, d] = edges[i];
if (max(dist[s][u], dist[v][t]) < INT_MAX) {
return min(dist[s][t], dist[s][u] + dist[v][t] + c);
} else {
return dist[s][t];
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
dist[i][j] = i == j ? 0 : INT_MAX;
}
}
for (int i = 0; i < m; ++i) {
auto &[u, v, c, d] = edges[i];
cin >> u >> v >> c >> d;
dist[u][v] = min(dist[u][v], c);
}
for (int k = 1; k <= n; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (max(dist[i][k], dist[k][j]) < INT_MAX) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
dijkstra(1, n, path_1);
dijkstra(n, 1, path_n);
int ans = max(dist[1][n], dist[n][1]) < INT_MAX ? dist[1][n] + dist[n][1] : INT_MAX;
for (int i = 0; i < m; ++i) {
auto &[u, v, c, d] = edges[i];
swap(u, v);
int dist_1 = path_1[i] ? dijkstra(1, n, path) : calc(1, n, i);
int dist_n = path_n[i] ? dijkstra(n, 1, path) : calc(n, 1, i);
if (max(dist_1, dist_n) < INT_MAX) {
ans = min(ans, dist_1 + dist_n + d);
}
swap(u, v);
}
cout << (ans < INT_MAX ? ans : -1) << "\n";
}
