#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=205;
const int M=50050;
const int inf=2e9+7;
struct Edge{int u,v,c,d;};
Edge edges[M];
bool bridge[M];
struct Bridges{
static const int NSZ=205;
vector<pair<int,int>> E[NSZ];
vector<int> ans;
int n,disc[NSZ],low[NSZ],tid;
void init(int _n){n=_n;tid=0;ans.clear();for(int i=1;i<=n;i++)E[i].clear(),disc[i]=low[i]=0;}
void AddEdge(int u,int v,int e){E[u].pb({v,e});E[v].pb({u,e});}
void DFS(int u,int p){
disc[u]=low[u]=++tid;
for(auto e:E[u])if(e.second!=p){
int v=e.first;
if(!disc[v]){
DFS(v,e.second);
if(low[v]>disc[u])ans.pb(e.second);
low[u]=min(low[u],low[v]);
}else low[u]=min(low[u],disc[v]);
}
}
}GPH;
void FindBridges(vector<pair<int,int>> go[],int st,int n){
GPH.init(n);
vector<bool> was(n+1,0);
function<void(int)> CNS=[&](int u){
was[u]=1;
for(auto e:go[u]){
GPH.AddEdge(u,e.first,e.second);
if(!was[e.first])CNS(e.first);
}
};
CNS(st);
GPH.DFS(st,-1);
//printf(":D\n");
for(int i:GPH.ans)bridge[i]=1;
}
struct DijkstraPQ{
static const int N=205;
int a[N],idx[N],val[N],n;
void init(int _n,int st,int inf){
n=_n;
for(int i=1;i<=n;i++)a[i]=i,val[i]=inf;
swap(a[st],a[1]);
for(int i=1;i<=n;i++)idx[a[i]]=i;
val[st]=0;
}
int size(){return n;}
void Change(int x,int f){
val[x]=f;
int p=idx[x];
while(p>1 && f<val[a[p/2]])a[p]=a[p/2],idx[a[p]]=p,p/=2;
a[p]=x;idx[x]=p;
}
int top(){return a[1];}
void pop(){
int now=1;
a[1]=a[n];n--;
idx[a[1]]=1;
while(now*2<=n){
int ch=now*2;
if(ch+1<=n && val[a[ch+1]]<val[a[ch]])ch++;
if(val[a[now]]<=val[a[ch]])break;
swap(a[now],a[ch]);
idx[a[now]]=now;
idx[a[ch]]=ch;
now=ch;
}
}
};
void Dijkstra(vector<pair<int,int>> E[],int n,int st,int dist[],vector<pair<int,int>> go[]){
for(int i=1;i<=n;i++)dist[i]=inf,go[i].clear();
DijkstraPQ pq;pq.init(n,st,inf);
dist[st]=0;
while(pq.size()){
int u=pq.top();
pq.pop();
for(auto e:E[u]){
int v=e.first,w=edges[e.second].c;
if(dist[v]>dist[u]+w){
dist[v]=dist[u]+w;
go[v].clear();
//pq.push({-dist[v],v});
pq.Change(v,dist[v]);
}
if(dist[v]==dist[u]+w)go[v].pb({u,e.second});
}
}
}
vector<pair<int,int>> E[N],R[N],T[N],go[N];
void BuildRev(int j,int m,int n){
for(int i=1;i<=n;i++)T[i].clear();
for(int i=1;i<=m;i++){
if(i!=j)T[edges[i].u].pb({edges[i].v,i});
else T[edges[i].v].pb({edges[i].u,i});
}
}
int dist[2][2][N],tmp[N];
int main(){
int n,m;
scanf("%i %i",&n,&m);
for(int i=1;i<=m;i++){
scanf("%i %i %i %i",&edges[i].u,&edges[i].v,&edges[i].c,&edges[i].d);
E[edges[i].u].pb({edges[i].v,i});
R[edges[i].v].pb({edges[i].u,i});
}
Dijkstra(E,n,1,dist[0][0],go);
FindBridges(go,n,n);
Dijkstra(R,n,n,dist[0][1],go);
Dijkstra(E,n,n,dist[1][0],go);
FindBridges(go,1,n);
Dijkstra(R,n,1,dist[1][1],go);
ll ans=(ll)dist[0][0][n]+dist[1][0][1];
for(int i=1;i<=m;i++){
if(bridge[i]){
BuildRev(i,m,n);
Dijkstra(T,n,1,tmp,go);
ll now=tmp[n];
if(now==inf)continue;
//printf("%i ",tmp[n]);
Dijkstra(T,n,n,tmp,go);
now+=tmp[1];
//printf("%i ",tmp[1]);
now+=edges[i].d;
ans=min(ans,now);
//printf("%i %lld\n",i,now);
}else{
int u=edges[i].u,v=edges[i].v,c=edges[i].c,d=edges[i].d;
ll d1=dist[0][0][n];
if(dist[0][0][v]<dist[0][0][u])d1=min(d1,(ll)dist[0][0][v]+c+dist[0][1][u]);
ll d2=dist[1][0][1];
if(dist[1][0][v]<dist[1][0][u])d2=min(d2,(ll)dist[1][0][v]+c+dist[1][1][u]);
ans=min(ans,d1+d2+d);
}
}
if(ans<inf)printf("%lld\n",ans);
else printf("-1\n");
return 0;
}
