//Autor: Bartłomiej Czarkowski
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif
struct edge {
int c, d;
};
const int N = 210;
const int M = 50100;
int n, m;
vector<edge> kr[N][N];
long long odp;
int odw[N];
long long v[2][N][N];
long long odl[2][2][N][N]; // czy obrócone krawędzie | z 1 / N | z wyłączeniem kogo | do kogo
void wylicz(long long odl[N], long long v[N][N], int src, int bez) {
for (int i = 1; i <= n; ++i) {
odl[i] = 1e18;
odw[i] = 0;
}
if (src == bez) {
return;
}
odw[bez] = 1;
odl[src] = 0;
for (int i = 1; i <= n; ++i) {
int x = 0;
long long od = 1e18;
for (int j = 1; j <= n; ++j) {
if (odw[j]) {
continue;
}
if (od > odl[j]) {
x = j;
od = odl[j];
}
}
if (!x) {
return;
}
odw[x] = 1;
for (int j = 1; j <= n; ++j) {
if (odw[j]) {
continue;
}
odl[j] = min(odl[j], odl[x] + v[x][j]);
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
v[0][i][j] = v[1][i][j] = 1e18;
}
}
for (int i = 1; i <= m; ++i) {
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
kr[a][b].push_back({c, d});
v[0][a][b] = min(v[0][a][b], (long long)c);
v[1][b][a] = min(v[1][b][a], (long long)c);
}
for (int i = 1; i <= n + 1; ++i) {
wylicz(odl[0][0][i], v[0], 1, i);
wylicz(odl[1][0][i], v[1], 1, i);
wylicz(odl[0][1][i], v[0], n, i);
wylicz(odl[1][1][i], v[1], n, i);
}
odp = odl[0][0][n + 1][n] + odl[0][1][n + 1][1]; // bez obracania krawędzi
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
// obracamy krawędź z i do j
vector<long long> cost;
cost.push_back(1e18);
for (auto k : kr[i][j]) {
cost.push_back(min(cost.back(), (long long)k.c));
}
long long suf = 1e18;
reverse(kr[i][j].begin(), kr[i][j].end());
for (auto k : kr[i][j]) {
cost.pop_back();
long long c1n1 = odl[0][0][j][i] + min(cost.back(), suf) + odl[1][1][i][j];
long long c1n2 = 1e18;
long long c1n3 = odl[0][0][i][j] + k.c + odl[1][1][j][i];
for (int g = 1; g <= n; ++g) {
c1n2 = min(c1n2, odl[0][0][j][g] + odl[1][1][i][g]);
}
long long cn11 = odl[0][1][j][i] + min(cost.back(), suf) + odl[1][0][i][j];
long long cn12 = 1e18;
long long cn13 = odl[0][1][i][j] + k.c + odl[1][0][j][i];
for (int g = 1; g <= n; ++g) {
cn12 = min(cn12, odl[0][1][i][g] + odl[1][0][j][g]);
}
odp = min(odp, c1n1 + cn11);
odp = min(odp, c1n1 + cn12);
odp = min(odp, c1n1 + cn13 + k.d);
odp = min(odp, c1n2 + cn11);
odp = min(odp, c1n2 + cn12);
odp = min(odp, c1n2 + cn13 + k.d);
odp = min(odp, c1n3 + cn11 + k.d);
odp = min(odp, c1n3 + cn12 + k.d);
odp = min(odp, c1n3 + cn13 + k.d);
suf = min(suf, (long long)k.c);
}
}
}
if (odp > 1e14) {
printf("-1\n");
return 0;
}
printf("%lld\n", odp);
return 0;
}
