#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
const ll MX = 1e15;
int n,m;
ll dist[205][205], dist1[205][205], dist2[205][205];
ll ind[205][205];
int fix[50005], fix1[50005], fix2[50005];
int X[50005],Y[50005];
ll c[50005], d[50005];
ll answer;
void rec(int x,int y,vector<int>&v){
ll k = ind[x][y];
if(k == MX){
return ;
}
if(k < 0){
v.pb(-k);
fix[-k] = 1;
return ;
}
rec(x,k,v);
rec(k,y,v);
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
dist[i][j] = MX;
dist1[i][j] = MX;
dist2[i][j] = MX;
ind[i][j] = MX;
}
}
for(int i = 1; i <= n; i++) {
dist[i][i] = 0;
dist1[i][i] = 0;
dist2[i][i] = 0;
}
for(int i = 1; i <= m; i++){
int x,y;
cin >> x >> y >> c[i] >> d[i];
dist[x][y] = min(dist[x][y], c[i]);
ind[x][y] = -i;
X[i] = x; Y[i] = y;
}
//disjkstra(1);
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
ll new_dist = dist[i][k] + dist[k][j];
if(dist[i][j] > new_dist){
dist[i][j] = new_dist;
ind[i][j] = k;
}
}
}
}
vector<int>path1, path2;
rec(1,n,path1);
for(int i = 1; i <= m; i++){
if(fix[i]){
fix[i] = 0;
continue;
}
int x = X[i], y = Y[i];
dist1[x][y] = min(dist1[x][y], c[i]);
}
//cout << "ok" << endl;
rec(n,1,path2);
for(int i = 1; i <= m; i++){
if(fix[i]){
fix[i] = 0;
continue;
}
int x = X[i], y = Y[i];
dist2[x][y] = min(dist2[x][y], c[i]);
}
//cout << "ok" << endl;
//for(auto x : path1) cout << x << " "; cout << endl;
//for(auto x : path2) cout << x << " "; cout << endl;
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
ll new_dist = dist1[i][k] + dist1[k][j];
if(dist1[i][j] > new_dist){
dist1[i][j] = new_dist;
}
new_dist = dist2[i][k] + dist2[k][j];
if(dist2[i][j] > new_dist){
dist2[i][j] = new_dist;
}
}
}
}
answer = dist[1][n] + dist[n][1];
for(int k = 0; k < (int)path1.size(); k++){
fix1[path1[k]] = 1;
int ind = path1[k];
int xx = X[ind];
int yy = Y[ind];
for(int i = 0; i <= k; i++){
for(int j = k; j < (int)path1.size(); j++){
int ind1 = path1[i];
int ind2 = path1[j];
int x = X[ind1], y = Y[ind2];
ll val = dist[n][yy] + c[ind] + dist[xx][1];
if(!fix2[ind]) val = min(dist[n][1], val);
ll new_dist = dist[1][x] + dist1[x][y] + dist[y][n] + d[path1[k]] + val;
//cout << x << " " << y << " " << new_dist << endl;
answer = min(answer, new_dist);
}
}
}
for(int k = 0; k < (int)path2.size(); k++){
fix2[path2[k]] = 1;
int ind = path2[k];
int xx = X[ind];
int yy = Y[ind];
for(int i = 0; i <= k; i++){
for(int j = k; j < (int)path2.size(); j++){
int ind1 = path2[i];
int ind2 = path2[j];
int x = X[ind1], y = Y[ind2];
ll val = dist[1][yy] + c[ind] + dist[xx][n];
if(!fix1[ind]) val = min(val, dist[1][n]);
ll new_dist = dist[n][x] + dist2[x][y] + dist[y][1] + val;
answer = min(answer, new_dist);
}
}
}
for(int i = 1; i <= m; i++){
if(fix1[i] || fix2[i])continue;
int x = X[i];
int y = Y[i];
ll new_dist = d[i] + min(dist[1][n], dist[1][y] + c[i] + dist[x][n]) + min(dist[n][1], dist[n][y] + c[i] + dist[x][1]);
//cout << x << " " << y << " " << new_dist << endl;
answer = min(answer, new_dist);
}
if(answer >= MX){
answer = -1;
}
if(answer < -1) {
cout << 1/0 << endl;
}
cout << answer << endl;
}
