#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),rg[i]=g[i];
vector<int> v;
F(n){
int tt=sz(g[i]);
Fi(j,tt){
mmp[{i,g[i][j].X.X}]=ind;
rr[ind]=g[i][j].X.X;
if(g[i][j].X.X==n-1)v.pb(ind);
g[i].pb({{ind,-1},g[i][j].Y});
g[ind]=rg[g[i][j].X.X];
Fi(k,sz(g[ind])){
if(g[ind][k].X.X!=i&&g[ind][k].X.Y==g[i][j].X.Y)g[ind][k].Y.Y-=g[i][j].Y.X;
//if(g[ind][k].Y.Y<0)cout<<"c "<<g[ind][k].X.X<<" "<<g[ind][k].X.Y<<" "<<g[ind][k].Y.X<<" "<<g[ind][k].Y.Y<<endl;;
}
ind++;
}
}
F(ind)d[i]=1e18;
for(int i=n;i<ind;i++){
for(auto pt:g[i]){
int u=mmp[{rr[i],pt.X.X}];
g[i].pb({{u,-1},{pt.Y}});
}
}
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{
pq.push({ss+pt.Y.Y,pt.X.X});
}
}
}
v.pb(n-1);
int ans=1e18;
//for(auto pt:g[6])cout<<pt.X.X<<" "<<pt.X.Y<<" "<<pt.Y.X<<" "<<pt.Y.Y<<endl;
//cout<<d[4]<<endl;
//F(n)cout<<d[i]<<" ";
//cout<<endl;
for(int i:v)ans=min(ans,d[i]);
cout<<(ans>1e17?-1:ans)<<endl;
return 0;
}
