#include<bits/stdc++.h>
using namespace std;
const int N=1500000009;
int a,b,c,d,e,i,j,ii,jj,zx,xc,C,D,A[50009],B[50009],dis[209][209],bo[50009],dis2[209][209],pas,z[209],zi,BO[50009],DIS[209][209],Adis[209][209];
pair <pair <int, int>, pair <int, int> > p[50009];
pair <int, int> P;
multiset <pair <pair <int, int>, int> > v[209],V[209];
multiset <pair <pair <int, int>, int> >::iterator it;
priority_queue <pair <int, int> > s;
void DJI(int q){
int h,qw,we,er;
for(h=1; h<=a; h++){
dis[q][h]=N;bo[h]=0;
}
while(s.size()) s.pop();
s.push({0,q});dis[q][q]=0;
while(s.size()){
while(s.size()){
P=s.top();
if(bo[P.second]==0) break;
s.pop();
}
if(s.size()==0) break;
qw=-P.first;we=P.second;bo[we]=1;
s.pop();
for(it=v[we].begin(); it!=v[we].end(); it++){
if(dis[q][(*it).first.first]>dis[q][we]+(*it).first.second){
dis[q][(*it).first.first]=dis[q][we]+(*it).first.second;
dis2[q][(*it).first.first]=(*it).second;
s.push({-dis[q][(*it).first.first],(*it).first.first});
}
}
}
}
void ADJI(int q){
int h,qw,we,er;
for(h=1; h<=a; h++){
Adis[q][h]=N;bo[h]=0;
}
while(s.size()) s.pop();
s.push({0,q});Adis[q][q]=0;
while(s.size()){
while(s.size()){
P=s.top();
if(bo[P.second]==0) break;
s.pop();
}
if(s.size()==0) break;
qw=-P.first;we=P.second;bo[we]=1;
s.pop();
for(it=V[we].begin(); it!=V[we].end(); it++){
if(Adis[q][(*it).first.first]>Adis[q][we]+(*it).first.second){
Adis[q][(*it).first.first]=Adis[q][we]+(*it).first.second;
s.push({-Adis[q][(*it).first.first],(*it).first.first});
}
}
}
}
//
void DJI2(int q){
int h,qw,we,er;
for(h=1; h<=a; h++){
DIS[q][h]=N;bo[h]=0;
}
while(s.size()) s.pop();
s.push({0,q});DIS[q][q]=0;
while(s.size()){
while(s.size()){
P=s.top();
if(bo[P.second]==0) break;
s.pop();
}
if(s.size()==0) break;
qw=-P.first;we=P.second;bo[we]=1;
s.pop();
for(it=v[we].begin(); it!=v[we].end(); it++){
if(DIS[q][(*it).first.first]>DIS[q][we]+(*it).first.second){
DIS[q][(*it).first.first]=DIS[q][we]+(*it).first.second;
s.push({-DIS[q][(*it).first.first],(*it).first.first});
}
}
}
}
//
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a>>b;
for(i=1; i<=b; i++){
cin>>c>>d>>C>>D;
p[i]={{c,d},{C,D}};
v[c].insert({{d,C},i});
V[d].insert({{c,C},i});
}
DJI(1);
DJI(a);
ADJI(1);
ADJI(a);
if(dis[1][a]!=N&&dis[a][1]!=N) pas=dis[1][a]+dis[a][1]; else pas=N;
if(1==0){
cout<<dis[1][a]<<" "<<dis[a][1]<<endl;
cout<<dis2[1][a]<<" "<<dis2[a][1]<<endl;
cout<<pas<<endl;
return 0;
}
for(i=1; i<=b; i++){
BO[i]=0;
}
c=a;zi=0;
while(c!=1&&c!=0){
zi++;z[zi]=dis2[1][c];
e=dis2[1][c];
if(p[e].first.first!=c){
c=p[e].first.first;
}else{
c=p[e].first.second;
}
}
for(i=1; i<=zi; i++) BO[z[i]]=1;
A[0]=dis[1][a];
for(i=1; i<=b; i++){
if(BO[i]==1) continue;
if(dis[1][p[i].first.second]!=N&&Adis[a][p[i].first.first]!=N) A[i]=dis[1][p[i].first.second]+p[i].second.first+Adis[a][p[i].first.first]; else A[i]=N;
A[i]=min(A[i],dis[1][a]);
}
for(i=1; i<=b; i++){
if(BO[i]==0) continue;
it=v[p[i].first.first].lower_bound({{p[i].first.second,p[i].second.first},i});
v[p[i].first.first].erase(it);
v[p[i].first.second].insert({{p[i].first.first,p[i].second.first},i});
DJI2(1);
A[i]=DIS[1][a];
it=v[p[i].first.second].lower_bound({{p[i].first.first,p[i].second.first},i});
v[p[i].first.second].erase(it);
v[p[i].first.first].insert({{p[i].first.second,p[i].second.first},i});
}
//
/*for(i=0; i<=b; i++){
cout<<A[i]<<"\n";
}*/
//
for(i=1; i<=b; i++){
BO[i]=0;
}
c=1;zi=0;
while(c!=a&&c!=0){
zi++;z[zi]=dis2[a][c];
e=dis2[a][c];
if(p[e].first.first!=c){
c=p[e].first.first;
}else{
c=p[e].first.second;
}
}
for(i=1; i<=zi; i++) BO[z[i]]=1;
B[0]=dis[a][1];
for(i=1; i<=b; i++){
if(BO[i]==1) continue;
if(dis[a][p[i].first.second]!=N&&Adis[1][p[i].first.first]!=N) B[i]=dis[a][p[i].first.second]+p[i].second.first+Adis[1][p[i].first.first]; else B[i]=N;
B[i]=min(B[i],dis[a][1]);
}
for(i=1; i<=b; i++){
if(BO[i]==0) continue;
it=v[p[i].first.first].lower_bound({{p[i].first.second,p[i].second.first},i});
v[p[i].first.first].erase(it);
v[p[i].first.second].insert({{p[i].first.first,p[i].second.first},i});
DJI2(a);
B[i]=DIS[a][1];
it=v[p[i].first.second].lower_bound({{p[i].first.first,p[i].second.first},i});
v[p[i].first.second].erase(it);
v[p[i].first.first].insert({{p[i].first.second,p[i].second.first},i});
}
//
/*for(i=0; i<=b; i++){
cout<<B[i]<<"\n";
}*/
//
for(i=0; i<=b; i++){
//pas=min(pas,A[i]+B[i]+p[i].second.second);
if(A[i]!=N&&B[i]!=N){
pas=min(pas,A[i]+B[i]+p[i].second.second);
}
}
if(pas!=N) cout<<pas; else cout<<-1;
return 0;
}
