#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fs first
#define sc second
#define pb push_back
void solve() {
int n,m;
cin>>n>>m;
vector<pair<pii,pii>> ed;
map<int,ll> sm[n+1];
for(int i=0;i<m;i++){
int x,y,c,p;
cin>>x>>y>>c>>p;
ed.pb({{x,y},{c,p}});
ed.pb({{y,x},{c,p}});
sm[x][c]+=p;
sm[y][c]+=p;
}
for(int i=1;i<=n;i++)ed.pb({{i,0},{0,0}});
sort(ed.begin(),ed.end());
// for(auto[p1,p2]:ed){
// cout<<p1.fs<<' '<<p1.sc<<' '<<p2.fs<<' '<<p2.sc<<'\n';
// }
int le[n+1],re[n+1],k=ed.size();
for(int i=0;i<k;i++){
if(!i||ed[i].fs.fs!=ed[i-1].fs.fs){
le[ed[i].fs.fs]=i;
}
if(i==k-1||ed[i].fs.fs!=ed[i+1].fs.fs){
re[ed[i].fs.fs]=i;
}
}
auto gid=[&](int x,int y){
pair<pii,pii> p={{x,y},{0,0}};
return lower_bound(ed.begin(),ed.end(),p)-ed.begin();
};
ll ds[k],ans=1e18;
bool vs[k];
memset(ds,63,sizeof(ds));
memset(vs,0,sizeof(vs));
priority_queue<pll> pq;
pq.push({0,0});
ds[0]=0;
while(!pq.empty()){
int v=pq.top().sc;
pq.pop();
if(vs[v])continue;
vs[v]=1;
auto[x,y]=ed[v].fs;
auto[c,p]=ed[v].sc;
// cout<<x<<' '<<y<<' '<<ds[v]<<'\n';
if(x==n){
cout<<ds[v]<<'\n';
return;
}
for(int u=le[x]+1;u<=re[x];u++){
int z=ed[u].fs.sc;
auto[c2,p2]=ed[u].sc;
{
int t=gid(z,x);
if(!vs[t]){
ds[t]=min(ds[t],ds[v]+p2);
pq.push({-ds[t],t});
}
}
{
int t=gid(z,0);
if(!vs[t]){
ds[t]=min(ds[t],ds[v]+sm[x][c2]-p2-(c==c2)*p);
pq.push({-ds[t],t});
}
}
}
}
cout<<"-1\n";
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
solve();
}
