#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
const int MX_N = 205;
const int MX_M = 5e4+5;
const long long INF = 1e18;
struct Edge { int v, c, d, i; };
int N, M;
vector<Edge> al[2][MX_N];
long long dist[4][MX_N];
void dijkstra(int s, vector<Edge>* al, long long* dist, int blocked) {
fill(dist+1,dist+1+N,INF);
dist[s] = 0;
bool done[N+1];
fill(done+1,done+1+N,0);
while (true) {
int u = -1;
FOR(v,1,N) if (!done[v] && (u == -1 || dist[v] < dist[u])) u = v;
if (u == -1) break;
done[u] = 1;
for (auto e : al[u]) if (e.i != blocked) {
if (dist[u] + e.c < dist[e.v]) {
dist[e.v] = dist[u] + e.c;
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
if (M <= 1000) {
FOR(i,1,M){
int U, V, C, D; cin >> U >> V >> C >> D;
al[0][U].push_back({V,C,D,i});
}
dijkstra(1,al[0],dist[0],-1);
dijkstra(N,al[0],dist[1],-1);
long long ans = min(INF, (long long) dist[0][N] + dist[1][1]);
FOR(u,1,N){
for (auto& e : al[0][u]) {
al[0][e.v].push_back({u,e.c,e.d,M+1});
dijkstra(1,al[0],dist[0],e.i);
dijkstra(N,al[0],dist[1],e.i);
al[0][e.v].pop_back();
ans = min(ans, (long long) dist[0][N] + dist[1][1] + e.d);
}
}
cout << (ans == INF ? -1 : ans) << '\n';
} else {
FOR(i,1,M){
int U, V, C, D; cin >> U >> V >> C >> D;
al[0][U].push_back({V,C,D,i});
al[1][V].push_back({U,C,D,M+i});
}
dijkstra(1,al[0],dist[0],-1);
dijkstra(1,al[1],dist[1],-1);
dijkstra(N,al[0],dist[2],-1);
dijkstra(N,al[1],dist[3],-1);
long long ans = min(INF, (long long) dist[0][N] + dist[2][1]);
FOR(u,1,N){
for (auto& e : al[0][u]) {
//TRACE(e.i _ dist[0][N] _ dist[2][e.v] _ dist[1][u] _ e.d);
//TRACE(e.i _ dist[0][e.v] _ dist[3][u] _ dist[2][1] _ e.d);
ans = min(ans, (long long) dist[0][N] + dist[2][e.v] + e.c + dist[1][u] + e.d);
ans = min(ans, (long long) dist[0][e.v] + e.c + dist[3][u] + dist[2][1] + e.d);
ans = min(ans, (long long) dist[0][e.v] + e.c + dist[3][u] + dist[2][e.v] + e.c + dist[1][u] + e.d);
}
}
cout << (ans == INF ? -1 : ans) << '\n';
}
}
