#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <climits>
using namespace std;
const int bign = 1e9;
signed main() {
cin.tie(0)->sync_with_stdio(0);
int n, m;
cin >> n >> m;
vector<vector<int>> elist;
elist.push_back({ 0, 0, 0, 0 });
vector<vector<int>> floyd(n, vector<int>(n, bign));
for (int i = 0; i < n; i++) {
floyd[i][i] = 0;
}
vector<vector<pair<int, int>>> adj(n, vector<pair<int, int>>());
for (int i = 0; i < m; i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
a--, b--;
elist.push_back({ a, b, c, d });
floyd[a][b] = min(floyd[a][b], c);
adj[a].emplace_back(b, c);
}
sort(elist.begin(), elist.end());
for (int times = 0; times < 6; times++)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
floyd[i][j] = min(floyd[i][j], floyd[i][k] + floyd[k][j]);
}
}
}
auto dijkstra = [&](vector<int>& visited, vector<int>& bef, int len, int in,
int from) {
priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>>
pqpii;
pqpii.push({ len, in, from });
while (!pqpii.empty()) {
vector<int> cur = pqpii.top();
pqpii.pop();
if (visited[cur[1]] != bign) continue;
visited[cur[1]] = cur[0];
bef[cur[1]] = cur[2];
for (auto a : adj[cur[1]])
pqpii.push({ a.second + cur[0], a.first, cur[1] });
}
};
auto dijkstra2 = [&](vector<int>& visited, int len, int in) {
priority_queue<pair<int, int>, vector<pair<int, int>>,
greater<pair<int, int>>>
pqpii;
pqpii.emplace(len, in);
while (!pqpii.empty()) {
pair<int, int> cur = pqpii.top();
pqpii.pop();
if (visited[cur.second] > cur.first) continue;
visited[cur.second] = cur.first;
for (auto a : adj[cur.second])
pqpii.push({ a.second + cur.first, a.first });
}
};
vector<int> visited(n, bign), bef1(n, -1), bef2(n, -1);
dijkstra(visited, bef1, 0, 0, -1);
vector<int> visited2(n, bign);
dijkstra(visited2, bef2, 0, n - 1, -1);
// if (visited[n - 1] == INT_MAX && visited2[0] == INT_MAX) {
// cout << "-1\n";
// return 0;
// }
vector<int> partof(m + 1);
if (visited[n - 1] != bign) {
vector<int> path1;
int cur = n - 1;
while (cur != -1) {
path1.push_back(cur);
cur = bef1[cur];
}
reverse(path1.begin(), path1.end());
for (int i = 0; i < path1.size() - 1; i++) {
int it = lower_bound(elist.begin(), elist.end(),
vector<int>({ path1[i], path1[i + 1], 0, 0 })) -
elist.begin();
partof[it] = 1;
}
}
if (visited2[n - 1] != bign) {
vector<int> path2;
int cur = 0;
while (cur != -1) {
path2.push_back(cur);
cur = bef2[cur];
}
reverse(path2.begin(), path2.end());
for (int i = 0; i < path2.size() - 1; i++) {
int it = lower_bound(elist.begin(), elist.end(),
vector<int>({ path2[i], path2[i + 1], 0, 0 })) -
elist.begin();
partof[it] = 1;
}
}
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// cout << floyd[i][j] << " ";
// }
// cout << "\n";
// }
int minans = INT_MAX;
for (int i = 0; i <= m; i++) {
if (partof[i]) {
int u = elist[i][0], v = elist[i][1], cst = elist[i][2],
price = elist[i][3];
adj[u].erase(find(adj[u].begin(), adj[u].end(), make_pair(v, cst)));
adj[v].emplace_back(u, cst);
visited = vector<int>(n, bign);
dijkstra2(visited, 0, 0);
if (visited[n - 1] == bign) {
adj[v].erase(find(adj[v].begin(), adj[v].end(), make_pair(u, cst)));
adj[u].emplace_back(v, cst);
continue;
}
price += visited[n - 1];
visited = vector<int>(n, bign);
dijkstra2(visited, 0, n - 1);
if (visited[0] == bign) {
adj[v].erase(find(adj[v].begin(), adj[v].end(), make_pair(u, cst)));
adj[u].emplace_back(v, cst);
continue;
}
price += visited[0];
minans = min(minans, price);
adj[v].erase(find(adj[v].begin(), adj[v].end(), make_pair(u, cst)));
adj[u].emplace_back(v, cst);
}
else {
vector<int> c1(floyd[0]), c2(floyd[n - 1]);
int u = elist[i][1], v = elist[i][0], cst = elist[i][2];
if (c1[u] != bign)
c1[v] = min(c1[v], c1[u] + cst);
if (c2[u] != bign)
c2[v] = min(c2[v], c2[u] + cst);
for (int j = 0; j < n; j++) {
if (floyd[v][j] != bign && c1[v] != bign)
c1[j] = min(c1[j], c1[v] + floyd[v][j]);
if (floyd[v][j] != bign && c2[v] != bign)
c2[j] = min(c2[j], c2[v] + floyd[v][j]);
}
// cout << i << " " << c1[n - 1] << " " << c2[0] << " " << elist[i][3] <<
// "\n";
if (c1[n - 1] != bign && c2[0] != bign)
minans = min(minans, c1[n - 1] + c2[0] + elist[i][3]);
}
}
if (minans == INT_MAX) {
cout << "-1\n";
}
else
cout << minans << "\n";
}
