#include <iostream>
#include <vector>
#include <tuple>
#include <set>
#include <cstring>
using namespace std;
using usi = unsigned int;
const usi INF = 1e8 + 1;
int n, m;
vector<tuple<int, int, usi, usi>> edges;
vector<vector<int>> g;
vector<vector<usi>> d;
set<int> imp_edges;
usi ssp(int start, int end, int flipped) {
usi d[n];
for (int i = 0; i < n; i++) {
d[i] = INF;
}
bool vis[n];
memset(vis, 0, sizeof vis);
d[start] = 0;
for (int _ = 0; _ < n; _++) {
int u = -1;
for (int i = 0; i < n; i++) {
if (not vis[i] and (u == -1 or d[i] < d[u])) u = i;
}
for (int i : g[u]) {
auto [a, b, w, c] = edges[i];
if (flipped == i) swap(a, b);
d[b] = min(d[b], d[u] + w);
}
vis[u] = 1;
}
return d[end];
}
void restoreEdges(int u, int start, bool vis[]) {
vis[u] = 1;
for (int i : g[u]) {
auto [a, b, w, c] = edges[i];
if (not vis[b] and d[start][b] == d[start][u] + w) {
imp_edges.insert(i);
restoreEdges(b, start, vis);
}
}
}
void getImpEdges() {
bool vis[n];
memset(vis, 0, sizeof vis);
restoreEdges(0, 0, vis);
memset(vis, 0, sizeof vis);
restoreEdges(n - 1, n - 1, vis);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
g.resize(n), edges.resize(m);
d.resize(n, vector<usi>(n, INF));
for (int i = 0; i < n; i++) {
d[i][i] = 0;
}
for (int i = 0; i < m; i++) {
auto &[a, b, w, c] = edges[i];
cin >> a >> b >> w >> c;
a--, b--;
g[a].push_back(i);
g[b].push_back(i);
d[a][b] = min(d[a][b], w);
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
getImpEdges();
// cout << "DUCK : " << endl;
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// cout << d[i][j] << ' ';
// }
// cout << endl;
// }
// cout << "FUCK : ";
// for (int i : imp_edges) {
// cout << i << ' ';
// }
// cout << endl;
usi ans;
if (d[0][n - 1] == INF or d[n - 1][0] == INF) ans = 4294967295;
else ans = d[0][n - 1] + d[n - 1][0]; // 0 0
for (int i = 0; i < m; i++) {
auto [a, b, w, c] = edges[i];
if (imp_edges.find(i) != imp_edges.end()) {
usi x = ssp(0, n - 1, i), y = ssp(n - 1, 0, i);
if (x != INF and y != INF) ans = min(ans, x + y + c);
continue;
}
if (d[0][n - 1] != INF and d[n - 1][a] != INF and d[b][0] != INF)
ans = min(ans, d[0][n - 1] + d[n - 1][a] + w + d[b][0] + c); // 0 1
if (d[0][n - 1] != INF and d[n - 1][b] != INF and d[a][0] != INF)
ans = min(ans, d[0][n - 1] + d[n - 1][b] + w + d[a][0] + c); // 0 2
if (d[0][a] != INF and d[b][n - 1] != INF and d[n - 1][0] != INF)
ans = min(ans, d[0][a] + w + d[b][n - 1] + d[n - 1][0] + c); // 1 0
if (d[0][a] != INF and d[b][n - 1] != INF and d[n - 1][a] != INF and d[b][0] != INF)
ans = min(ans, d[0][a] + w + d[b][n - 1] + d[n - 1][a] + w + d[b][0] + c); // 1 1
if (d[0][a] != INF and d[b][n - 1] != INF and d[n - 1][b] != INF and d[a][0] != INF)
ans = min(ans, d[0][a] + w + d[b][n - 1] + d[n - 1][b] + w + d[a][0] + c); // 1 2
if (d[0][b] != INF and d[a][n - 1] != INF and d[n - 1][0] != INF)
ans = min(ans, d[0][b] + w + d[a][n - 1] + d[n - 1][0] + c); // 2 0
if (d[0][b] != INF and d[a][n - 1] != INF and d[n - 1][a] != INF and d[b][0] != INF)
ans = min(ans, d[0][b] + w + d[a][n - 1] + d[n - 1][a] + w + d[b][0] + c); // 2 1
if (d[0][b] != INF and d[a][n - 1] != INF and d[n - 1][b] != INF and d[a][0] != INF)
ans = min(ans, d[0][b] + w + d[a][n - 1] + d[n - 1][b] + w + d[a][0] + c); // 2 2
}
if (ans == 4294967295) cout << -1 << '\n';
else cout << ans << '\n';
return 0;
}
