#include <bits/stdc++.h>
using namespace std;
inline long long read(){
long long c=1,f=0;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
c=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
f=f*10+(ch-'0');
ch=getchar();
}
return c*f;
}
inline void write(__int128 x){
if(x<0){
putchar('-');
x=-1*x;
}
if(x>9){
write(x/10);
}
putchar('0'+x%10);
return;
}
struct node{
long long id;
long long d;
bool operator > (node b)const{
return d>b.d;
}
};
priority_queue<node,vector<node>,greater<node> >q;
long long n,m,w[50005],ne[50005],h[205],tot,d[50005],f[205],g[205];
long long w1[50005],ne1[50005],h1[205],tot1,d1[50005],v[50005];
long long pref[205],preg[205],ans[50005],dis1[205],dis2[205],minn;
bool vis[50005],flag[205],isok[205];
void add(long long a,long long b,long long c){
w[++tot]=b;
d[tot]=c;
ne[tot]=h[a];
h[a]=tot;
return;
}
void add1(long long a,long long b,long long c){
w1[++tot1]=b;
d1[tot1]=c;
ne1[tot1]=h1[a];
h1[a]=tot1;
return;
}
void dijstra(long long u){
for(int i=1;i<=n;i++){
f[i]=1e18;
flag[i]=false;
}
f[u]=0;
node temp;
temp.id=u;
temp.d=0;
q.push(temp);
while(!q.empty()){
node p=q.top();
q.pop();
if(flag[p.id]){
continue;
}
flag[p.id]=true;
for(int i=h[p.id];i;i=ne[i]){
if(isok[i]){
continue;
}
temp.id=w[i];
temp.d=p.d+d[i];
if(f[temp.id]>temp.d){
f[temp.id]=temp.d;
pref[temp.id]=i;
q.push(temp);
}
}
}
return;
}
void dijstra1(long long u){
for(int i=1;i<=n;i++){
g[i]=1e18;
flag[i]=false;
}
g[u]=0;
node temp;
temp.id=u;
temp.d=0;
q.push(temp);
while(!q.empty()){
node p=q.top();
q.pop();
if(flag[p.id]){
continue;
}
flag[p.id]=true;
for(int i=h1[p.id];i;i=ne1[i]){
if(isok[i]){
continue;
}
temp.id=w1[i];
temp.d=p.d+d1[i];
if(g[temp.id]>temp.d){
g[temp.id]=temp.d;
preg[temp.id]=i;
q.push(temp);
}
}
}
return;
}
int main(){
// freopen("sets.in","r",stdin);
// freopen("sets.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
n=read();m=read();
for(int i=1;i<=m;i++){
long long a,b,c;
a=read();b=read();c=read();v[i]=read();
add(a,b,c);
add1(b,a,c);
}
dijstra(1);
dijstra1(n);
minn=f[n];
for(int i=1;i<=n;i++){
dis1[i]=f[i];dis2[i]=g[i];
}
for(int i=1;i<=n;i++){
vis[pref[i]]=vis[preg[i]]=true;
}
for(int i=1;i<=n;i++){
for(int j=h[i];j;j=ne[j]){
if(vis[j]==false){
ans[j]=min(dis1[w[j]]+dis2[i]+d[j],dis1[n]);
}
else{
isok[j]=true;
add(w[j],i,d[j]);
dijstra(1);
h[w[j]]=ne[tot];
tot--;
isok[j]=false;
ans[j]=f[n];
}
}
}
memset(vis,false,sizeof(vis));
memset(pref,0,sizeof(pref));
memset(preg,0,sizeof(preg));
dijstra(n);
dijstra1(1);
minn+=f[1];
for(int i=1;i<=n;i++){
dis1[i]=f[i];dis2[i]=g[i];
}
for(int i=1;i<=n;i++){
vis[pref[i]]=vis[preg[i]]=true;
}
for(int i=1;i<=n;i++){
for(int j=h[i];j;j=ne[j]){
if(vis[j]==false){
ans[j]+=min(dis1[w[j]]+dis2[i]+d[j],dis1[1]);
}
else{
isok[j]=true;
add(w[j],i,d[j]);
dijstra(n);
h[w[j]]=ne[tot];
tot--;
isok[j]=false;
ans[j]+=f[1];
}
}
}
for(int i=1;i<=m;i++){
minn=min(minn,ans[i]+v[i]);
}
if(minn>=1e18){
minn=-1;
}
printf("%lld",minn);
// fclose(stdin);
// fclose(stdout);
return 0;
}
