#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
const int MXN = 205, MXM = 50005;
int apsp[MXN][MXN];
int eds[MXM][4];
vector<int> adj[MXN];
int mxh = INT_MAX * 1000ll;
int dist(int src, int dest, int skip) {
int dists[MXN];
for (int i=0; i<MXN; i++) dists[i] = mxh;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> proc;
proc.push({0, src});
while (!proc.empty()) {
auto x = proc.top(); proc.pop();
int di = x.first, no = x.second;
if (dists[no] < di) continue;
dists[no] = di;
for (auto ed: adj[no]) {
if (ed != skip) {
int ot = eds[ed][0] + eds[ed][1] - no;
int we = eds[ed][2];
if (dists[ot] > dists[no] + we) {
dists[ot] = dists[no] + we;
proc.push({dists[ot], ot});
}
}
}
if (no == eds[skip][1]) {
int ot = eds[skip][0];
int od = dists[no] + eds[skip][2];
if (dists[ot] > od) {
dists[ot] = od;
proc.push({od, ot});
}
}
}
return dists[dest];
}
signed main() {
for (int i=0; i<MXN; i++) {
for (int j=0; j<MXN; j++) {
apsp[i][j] = mxh;
}
apsp[i][i] = 0;
}
cin >> n >> m;
for (int i=0; i<m; i++) {
int a, b, w, c;
cin >> a >> b >> w >> c;
eds[i][0] = a;
eds[i][1] = b;
eds[i][2] = w;
eds[i][3] = c;
adj[a].push_back(i);
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 res = apsp[1][n] + apsp[n][1];
for (int i=0; i<m; i++) {
int a = eds[i][0], b = eds[i][1];
int w = eds[i][2], c = eds[i][3];
int d1 = min(apsp[1][n], apsp[1][b] + w + apsp[a][n]);
int d2 = min(apsp[n][1], apsp[n][b] + w + apsp[a][1]);
if (d1 + c + d2 < res) {
int actual = dist(1, n, i) + dist(n, 1, i) + c;
res = min(res, actual);
}
}
if (res >= mxh) cout << -1 << endl;
else cout << res << endl;
}
