#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
typedef long long ll;
#define st first
#define nd second
#define f(a, c, b) for (int a = c; b > a; a++)
#define pb push_back
#define all(a) a.begin(), a.end()
const ll DUZO = 1'000'000'000'000'000'000;
ll wnk = DUZO;
int n, m;
vector<pair<pair<int, int>, pair<ll, ll>>> krawedzie;
vector<vector<ll>> odl;
vector<vector<int>> ile; //ile minimalnych krawedzi wychodzi z i do j
vector<vector<pair<ll, ll>>> macierz_sasiedztwa;
vector<ll> wyniki_dijkstra;
ll dijkstra(int zrodlo) {
f(i, 1, n + 1) {
wyniki_dijkstra[i] = -1;
}
priority_queue<pair<ll, int>> kolejka;
kolejka.push({0, zrodlo});
pair<ll, int> p1;
while (!kolejka.empty()) {
p1 = kolejka.top();
kolejka.pop();
if (wyniki_dijkstra[p1.nd] != -1) continue;
wyniki_dijkstra[p1.nd] = -p1.st;
f(i, 1, n + 1) {
if (wyniki_dijkstra[i] != -1 || i == p1.nd || macierz_sasiedztwa[p1.nd][i].st == -1) continue;
kolejka.push({p1.st - macierz_sasiedztwa[p1.nd][i].st, i});
}
}
if (zrodlo == 1) return wyniki_dijkstra[n];
return wyniki_dijkstra[1];
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
int w1, w2;
ll w3, w4;
odl.resize(n + 1, vector<ll>(n + 1, DUZO));
f(i, 1, (n + 1)) odl[i][i] = 0;
f(i, 0, m) {
cin >> w1 >> w2 >> w3 >> w4;
krawedzie.pb({{w1, w2}, {w3, w4}});
odl[w1][w2] = min(odl[w1][w2], w3);
}
f(k, 1, (n + 1)) f(u, 1, (n + 1)) f(v, 1, (n + 1)) odl[u][v] = min(odl[u][v], odl[u][k] + odl[k][v]);
ile.resize(n + 1, vector<int>(n + 1, 0));
macierz_sasiedztwa.resize(n + 1, vector<pair<ll, ll>>(n, {DUZO, DUZO}));
for (pair<pair<int, int>, pair<ll, ll>> ele: krawedzie) {
if (macierz_sasiedztwa[ele.st.st][ele.st.nd].st > ele.nd.st) {
macierz_sasiedztwa[ele.st.st][ele.st.nd].nd = macierz_sasiedztwa[ele.st.st][ele.st.nd].st;
macierz_sasiedztwa[ele.st.st][ele.st.nd].st = ele.nd.st;
}
macierz_sasiedztwa[ele.st.st][ele.st.nd].nd = min(macierz_sasiedztwa[ele.st.st][ele.st.nd].nd, ele.nd.st);
}
f(i, 1, n + 1) {
f(j, 1, n + 1) {
f(k, 1, n + 1) {
if (macierz_sasiedztwa[i][k].st <= 1'000'000 && ((macierz_sasiedztwa[i][k].st + odl[k][j]) == odl[i][j])) ile[i][j]++;
if (macierz_sasiedztwa[i][k].nd <= 1'000'000 && ((macierz_sasiedztwa[i][k].nd + odl[k][j]) == odl[i][j])) ile[i][j]++;
}
}
}
pair<ll, ll> p1;
pair<ll, ll> p2;
wyniki_dijkstra.resize(n + 1);
for (pair<pair<int, int>, pair<ll, ll>> ele: krawedzie) {
if (((odl[1][ele.st.st] + ele.nd.st + odl[ele.st.nd][n]) > odl[1][n]) && (ile[ele.st.st][n] > 1)) {
wnk = min(wnk, odl[1][n] + odl[n][ele.st.nd] + odl[ele.st.st][1] + ele.nd.st + ele.nd.nd);
} else {
if (macierz_sasiedztwa[ele.st.nd][ele.st.st].st > ele.nd.st) {
p1 = macierz_sasiedztwa[ele.st.nd][ele.st.st];
p2 = macierz_sasiedztwa[ele.st.st][ele.st.nd];
macierz_sasiedztwa[ele.st.nd][ele.st.st].st = ele.nd.st;
if (macierz_sasiedztwa[ele.st.st][ele.st.nd].st == ele.nd.st) {
macierz_sasiedztwa[ele.st.st][ele.st.nd].st = macierz_sasiedztwa[ele.st.st][ele.st.nd].nd;
}
wnk = min(wnk, dijkstra(1) + dijkstra(n) + ele.nd.nd);
macierz_sasiedztwa[ele.st.nd][ele.st.st] = p1;
macierz_sasiedztwa[ele.st.st][ele.st.nd] = p2;
}
}
}
if (wnk >= (2'000'000'000)) {
cout << -1 << "\n";
} else {
cout << wnk << "\n";
}
return 0;
}
