#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
const int MXN = 205, MXM = 50005;
vector<pair<pair<int, int>, pair<int, int>>> eds;
vector<pair<pair<int, int>, pair<int, int>>> adj[MXN];
int par[MXN];
int dist1n[MXM];
int distn1[MXM];
int dist[MXN];
bool onpath[MXM];
bool onpath2[MXM];
int apsp[MXN][MXN];
int block = -1;
int get_dist(int src, int dest, int blo) {
block = blo;
memset(onpath, 0, sizeof onpath);
for (int i=1; i<=n; i++) {
dist[i] = LLONG_MAX / 10;
par[i] = -1;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> proc;
proc.push({0, src});
while (!proc.empty()) {
pair<int, int> tr = proc.top();
proc.pop();
int no = tr.second;
int di = tr.first;
if (dist[no] < di) continue;
dist[no] = di;
for (auto x: adj[no]) {
int ad = x.first.first;
int ind = x.first.second;
int we = x.second.first;
if (ind == block) continue;
if (dist[no] + we < dist[ad]) {
dist[ad] = dist[no] + we;
par[ad] = ind;
proc.push({dist[ad], ad});
}
}
}
for (int i=1; i<=n; i++) {
if (par[i] == -1) continue;
onpath[par[i]] = true;
}
return dist[dest];
}
signed main() {
cin >> n >> m;
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
apsp[i][j] = LLONG_MAX / 10;
if (i == j) apsp[i][j] = 0;
}
}
for (int i=0; i<m; i++) {
int a, b, w, f;
cin >> a >> b >> w >> f;
eds.push_back({{a, b}, {w, f}});
adj[a].push_back({{b, i}, {w, f}});
apsp[a][b] = min(apsp[a][b], w);
}
for (int k=1; k<=n; k++) {
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
if (apsp[i][k] + apsp[k][j] < apsp[i][j]) {
apsp[i][j] = apsp[i][k] + apsp[k][j];
}
}
}
}
int cr = get_dist(1, n, -1);
for (int i=0; i<m; i++) {
onpath2[i] = onpath[i];
}
dist1n[m] = cr;
for (int i=0; i<m; i++) {
if (!onpath2[i]) {
dist1n[i] = cr;
}
else {
block = i;
dist1n[i] = get_dist(1, n, i);
}
}
cr = get_dist(n, 1, -1);
for (int i=0; i<m; i++) {
onpath2[i] = onpath[i];
}
distn1[m] = cr;
for (int i=0; i<m; i++) {
if (!onpath2[i]) {
distn1[i] = cr;
}
else {
block = i;
distn1[i] = get_dist(n, 1, i);
}
}
int mn = apsp[1][n] + apsp[n][1];
for (int i=0; i<m; i++) {
int a = eds[i].first.first, b = eds[i].first.second;
int w = eds[i].second.first, f = eds[i].second.second;
mn = min(mn, f + apsp[1][a] + w + apsp[b][n] + distn1[i]);
mn = min(mn, f + apsp[1][b] + w + apsp[a][n] + distn1[i]);
mn = min(mn, f + apsp[n][a] + w + apsp[b][1] + dist1n[i]);
mn = min(mn, f + apsp[n][b] + w + apsp[a][1] + dist1n[i]);
}
if (mn >= LLONG_MAX / 10) cout << -1 << endl;
else cout << mn << endl;
}
