#include <iostream>
#include <vector>
#include <set>
#include <tuple>
#include <cstring>
using namespace std;
using ll = long long;
const ll INF = 1e16;
int n, m;
tuple<int, int, ll, ll> edges[50001];
vector<int> g[201];
ll d[201][201];
bool special[50001];
ll ssp(int start, int end, int flipped) {
ll 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) {
special[i] = 1;
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;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
d[i][j] = INF;
}
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;
ll 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 (special[i]) {
ans = min(ans, ssp(0, n - 1, i) + ssp(n - 1, 0, i) + c);
continue;
}
ans = min(ans, d[0][n - 1] + d[n - 1][a] + w + d[b][0] + c); // 0 1
ans = min(ans, d[0][n - 1] + d[n - 1][b] + w + d[a][0] + c); // 0 2
ans = min(ans, d[0][a] + w + d[b][n - 1] + d[n - 1][0] + c); // 1 0
ans = min(ans, d[0][a] + w + d[b][n - 1] + d[n - 1][a] + w + d[b][0] + c); // 1 1
ans = min(ans, d[0][a] + w + d[b][n - 1] + d[n - 1][b] + w + d[a][0] + c); // 1 2
ans = min(ans, d[0][b] + w + d[a][n - 1] + d[n - 1][0] + c); // 2 0
ans = min(ans, d[0][b] + w + d[a][n - 1] + d[n - 1][a] + w + d[b][0] + c); // 2 1
ans = min(ans, d[0][b] + w + d[a][n - 1] + d[n - 1][b] + w + d[a][0] + c); // 2 2
}
cout << (ans < INF ? ans : -1) << '\n';
return 0;
}
