#include <bits/stdc++.h>
#define DIMN 210
#define INF 2000000000
using namespace std;
int dp[2][DIMN][50010];
priority_queue <pair < pair <int , int > , pair <int , int > > > h;
vector <pair <int , pair <int , int > > > v[DIMN];
struct idk{
int x , y , z , c;
} mch[50010];
char buff[5000000];
int pos , n;
int getnr(){
int nr = 0;
while ('0' > buff[pos] || buff[pos] > '9')
pos++;
while ('0' <= buff[pos] && buff[pos] <= '9'){
nr = nr * 10 + buff[pos] - '0';
pos++;
}
return nr;
}
int not_worth_it (int stare , int nod , int taken){
if (stare == 0 && dp[1][n][taken] < dp[stare][nod][taken])
return 1;
return 0;
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int m , x , y , z , c , i , dist , nod , vecin , cost , stare , j , taken , cnt = 0;
fread (buff , 1 , 5000000 , fin);
n = getnr();
m = getnr();
for (i = 1 ; i <= m ; i++){
x = getnr();
y = getnr();
z = getnr();
c = getnr();
v[x].push_back(make_pair(y , make_pair(z , i)));
mch[i] = {x , y , z , c};
}
/// acum faci cele 2 dijkstra uri
for (i = 1 ; i <= n ; i++)
for (j = 0 ; j <= m ; j++)
dp[0][i][j] = dp[1][i][j] = INF;
for (j = 0 ; j <= m ; j++){
dp[0][1][j] = mch[j].c;
h.push(make_pair(make_pair(-mch[j].c , 1) , make_pair(0 , j)));
}
while (!h.empty()){
dist = -h.top().first.first;
nod = h.top().first.second;
stare = h.top().second.first;
taken = h.top().second.second;
h.pop();
if (dp[stare][nod][taken] != dist || not_worth_it(stare , nod , taken) || cnt == m + 1)
continue;
if (nod == n)
cnt++;
if (nod == 1 && stare == 1){
fprintf (fout,"%d",dist);
return 0;
}
//printf ("%d %d %d %d\n" , nod , stare , taken , dist);
if (nod == mch[taken].y){ /// caz particular, parcurg muchia intoarsa
/// parcurgi muchia inversa
vecin = mch[taken].x;
cost = mch[taken].z;
if (vecin == n && stare == 0){
/// cazul cand se schimba starea
if (dp[1][vecin][taken] > dist + cost){
dp[1][vecin][taken] = dist + cost;
h.push(make_pair( make_pair( -dp[1][vecin][taken] , vecin ) , make_pair( 1 , taken ) ));
}
}
else {
if (dp[stare][vecin][taken] > dist + cost){
dp[stare][vecin][taken] = dist + cost;
h.push(make_pair( make_pair( -dp[stare][vecin][taken] , vecin ) , make_pair( stare , taken ) ));
}
}
}
for (i = 0 ; i < v[nod].size() ; i++){
vecin = v[nod][i].first;
cost = v[nod][i].second.first;
if (v[nod][i].second.second == taken)
continue;
if (vecin == n && stare == 0){
/// cazul cand se schimba starea
if (dp[1][vecin][taken] > dist + cost){
dp[1][vecin][taken] = dist + cost;
h.push(make_pair( make_pair( -dp[1][vecin][taken] , vecin ) , make_pair( 1 , taken ) ));
}
}
else {
if (dp[stare][vecin][taken] > dist + cost){
dp[stare][vecin][taken] = dist + cost;
h.push(make_pair( make_pair( -dp[stare][vecin][taken] , vecin ) , make_pair( stare , taken ) ));
}
}
}
}
fprintf (fout,"-1");
return 0;
}
