#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int,int>
#define X first
#define Y second
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define abs(x) ((x)>0?(x):-(x))
#define pb push_back
int n,m,ind,rr[2000010],d[2000010];
vector<pair<pii,pii> >g[2000010],rg[2000010];
map<pii,int> mmp;
bool used[2000010];
void calc(int x){
map<int,int> mp;
for(auto pt:g[x]){
mp[pt.X.Y]+=pt.Y.X;
}
F(sz(g[x])){
g[x][i].Y.Y=mp[g[x][i].X.Y]-g[x][i].Y.X;
}
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
ind=n;
F(m){
int a,b,c,d;
cin>>a>>b>>c>>d;
--a,--b;
g[a].pb({{b,c},{d,0}});
g[b].pb({{a,c},{d,0}});
}
F(n)calc(i);
vector<int> v;
F(n){
int tt=sz(g[i]);
Fi(j,tt){
if(!mmp.count(g[i][j].X)){if(g[i][j].X.X==n-1)v.pb(ind);mmp[g[i][j].X]=ind++;}
int ttt=mmp[g[i][j].X];
//cout<<"CCC "<<ttt<<endl;
g[i].pb({{ttt,g[i][j].X.Y},{g[i][j].Y.X,g[i][j].Y.Y}});
g[ttt].pb({{i,g[i][j].X.Y},{g[i][j].Y.X,0}});
}
}
for(int i=n;i<ind;i++)calc(i);
for(int i=n;i<ind;i++){
int tt=sz(g[i]);
Fi(j,tt){
pair<pii,pii> pt=g[i][j];
int u=mmp[pt.X];
pii ptt=pt.Y;
ptt.Y=max(0ll,ptt.Y-1);
g[i].pb({{u,-1},ptt});
}
}
F(ind)d[i]=1e18;
priority_queue<pii,vector<pii>,greater<pii> >pq;
pq.push({0,0});
memset(used,0,sizeof(used));
while(!pq.empty()){
int p=pq.top().Y,ss=pq.top().X;pq.pop();
if(used[p])continue;
d[p]=ss;
//cout<<"a "<<p<<" "<<ss<<endl;
used[p]=1;
for(auto pt:g[p]){
if(pt.X.X>=n){
pq.push({ss+pt.Y.X,pt.X.X});
}
else{
// cout<<"cc "<<pt.Y.Y<<" "<<pt.X.X<<endl;
if(pt.Y.Y<=1)pq.push({ss+pt.Y.Y,pt.X.X});
}
}
}
v.pb(n-1);
//for(auto pt:g[0])cout<<pt.X.X<<" "<<pt.X.Y<<" "<<pt.Y.X<<" "<<pt.Y.Y<<endl;
int ans=1e18;
for(int i:v)ans=min(ans,d[i]);
cout<<(ans>1e17?-1:ans)<<endl;
return 0;
}
