#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 203;
const int MAXM = 50003;
int n, m;
pair<pair<int, int>, pair<int, int>> krawedzie[MAXM];
vector<int> sasiedzi[MAXN]; //indeksy krawedzi
bool odwiedzone[MAXN];
int wynik_dijkstra[MAXN];
int dijkstra(int skad, int dokad, int ind) {
for (int i = 0; MAXN > i; i++) {
odwiedzone[i] = false;
wynik_dijkstra[i] = -1;
}
priority_queue<pair<int, int>> kopiec;
kopiec.push({0, skad});
pair<int, int> p1;
int aktl_v, aktl_koszt;
while (!kopiec.empty()) {
p1 = kopiec.top();
kopiec.pop();
aktl_koszt = -p1.first;
aktl_v = p1.second;
if (odwiedzone[aktl_v]) continue;
odwiedzone[aktl_v] = true;
wynik_dijkstra[aktl_v] = aktl_koszt;
if (aktl_v == krawedzie[ind].first.second) {
if (!odwiedzone[krawedzie[ind].first.first]) {
kopiec.push({-(aktl_koszt + krawedzie[ind].second.first), krawedzie[ind].first.first});
}
}
for (int sasd: sasiedzi[aktl_v]) {
if (odwiedzone[krawedzie[ind].first.second]) continue;
if (sasd == ind) continue;
kopiec.push({-(aktl_koszt + krawedzie[sasd].second.first), krawedzie[sasd].first.second});
}
}
return wynik_dijkstra[dokad];
}
int zrob(int ind) {
int p1;
int wynik = krawedzie[ind].second.second;
p1 = dijkstra(1, n, ind);
if (p1 == -1) return 2000000000;
wynik += p1;
p1 = dijkstra(n, 1, ind);
if (p1 == -1) return 2000000000;
wynik += p1;
return wynik;
}
int main() {
//ios_base::sync_with_stdio(0);
//cin.tie(0);
cin >> n >> m;
int w1, w2, w3, w4;
for (int i = 0; m > i; i++) {
cin >> w1 >> w2 >> w3 >> w4;
krawedzie[i] = {{w1, w2}, {w3, w4}};
sasiedzi[w1].push_back(i);
}
int p1;
int wynik;
p1 = dijkstra(1, n, MAXM - 1);
if (p1 == -1) {
wynik = 2000000000;
} else {
wynik = p1;
p1= dijkstra(n, 1, MAXM - 1);
if (p1 == -1) {
wynik = 2000000000;
} else {
wynik += p1;
}
}
for (int i = 0; m > i; i++) {
wynik = min(wynik, zrob(i));
}
if (wynik == 2000000000) wynik = -1;
cout << wynik;
return 0;
}
