#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 201;
const int M = 50001;
const ll INF = 1e10;
struct edge{
int u, v, c, d, ind;
};
int n, m;
edge eds[M];
ll dist[N][N], f[2][M], minDist[N];
int trace[N][N];
vector <edge> adj[N];
void ReadInput(){
cin >> n >> m;
for(int i = 1; i <= 2 * n; i++)
for(int j = 1; j <= 2 * n; j++)
dist[i][j] = (i != j) * INF;
for(int i = 1; i <= m; i++){
cin >> eds[i].u >> eds[i].v >> eds[i].c >> eds[i].d;
eds[i].ind = i;
}
}
ll Dijkstra(int s, int t, int revInd = 0){
for(int i = 1; i <= n; i++)
minDist[i] = INF;
typedef pair<int, int> data;
priority_queue <data, vector<data>, greater<data>> pq;
minDist[s] = 0;
pq.push({0, s});
while (!pq.empty()){
int u = pq.top().second;
int d = pq.top().first;
pq.pop();
if (minDist[u] != d)
continue;
if (u == t)
return minDist[u];
for(auto e : adj[u])
if (e.ind != revInd && minDist[e.v] > minDist[e.u] + e.c){
minDist[e.v] = minDist[e.u] + e.c;
pq.push({minDist[e.v], e.v});
}
if (eds[revInd].v == u && minDist[eds[revInd].u] > minDist[u] + eds[revInd].c){
minDist[eds[revInd].u] = minDist[u] + eds[revInd].c;
pq.push({minDist[eds[revInd].u], eds[revInd].u});
}
}
return INF;
}
void Solve(){
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
dist[i][j] = (i != j) * INF;
for(int i = 1; i <= m; i++){
if (dist[eds[i].u][eds[i].v] > eds[i].c){
dist[eds[i].u][eds[i].v] = eds[i].c;
trace[eds[i].u][eds[i].v] = i;
}
adj[eds[i].u].push_back(eds[i]);
}
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if (dist[i][j] > dist[i][k] + dist[k][j]){
dist[i][j] = dist[i][k] + dist[k][j];
trace[i][j] = trace[i][k];
}
int s = 1, t = n;
for(int num = 0; num < 2; num++){
for(int i = 1; i <= m; i++)
f[num][i] = min(dist[s][t], dist[s][eds[i].v] + eds[i].c + dist[eds[i].u][t]);
if (dist[s][t] != INF){
cerr << num << endl;
int u = s;
while (u != t){
int ind = trace[u][t];
f[num][ind] = Dijkstra(s, t, ind);
u = eds[ind].v;
}
}
swap(s, t);
}
ll ans = dist[1][n] + dist[n][1];
for(int i = 1; i <= m; i++)
ans = min(ans, f[0][i] + f[1][i] + eds[i].d);
cout << (ans < INF? ans : -1);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
ReadInput();
Solve();
return 0;
}
