#include<bits/stdc++.h>
using namespace std;
struct edge { int pos,id,val; };
bool comp(edge a,edge b) { return a.id<b.id; }
const int MAXN=13e5+5;
const long long INF=1e18;
map< pair<int,int>,int > mp;
vector<edge> ds[MAXN];
vector< pair<int,long long> > E[MAXN];
long long dp[MAXN];
int pos[MAXN];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int l,r,c,v;
cin>>l>>r>>c>>v;
ds[l].push_back({r,c,v}),ds[r].push_back({l,c,v});
}
int cnt=0;
for(int i=1;i<=n;i++)
{
pos[i]=++cnt;
int sz=ds[i].size(),pre=0;
sort(ds[i].begin(),ds[i].end(),comp);
for(int j=1;j<=sz;j++) if(j==sz||ds[i][j].id!=ds[i][j-1].id)
{
long long sum=0;
for(int k=pre;k<j;k++) sum+=ds[i][k].val;
for(int k=pre;k<j;k++) E[pos[i]].push_back({mp[{i,ds[i][k].pos}]=++cnt,ds[i][k].val});
pre=j;
}
}
for(int i=1;i<=n;i++) for(auto v:ds[i]) E[mp[{i,v.pos}]].push_back({pos[v.pos],0});
for(int i=1;i<=n;i++)
{
int sz=ds[i].size(),pre=0;
for(int j=1;j<=sz;j++) if(j==sz||ds[i][j].id!=ds[i][j-1].id)
{
cnt++;
long long sum=0;
for(int k=pre;k<j;k++) sum+=ds[i][k].val;
for(int k=pre;k<j;k++)
{
E[cnt].push_back({pos[ds[i][k].pos],sum-ds[i][k].val});
E[mp[{ds[i][k].pos,i}]].push_back({cnt,-ds[i][k].val});
}
E[pos[i]].push_back({cnt,0}),pre=j;
}
}
for(int i=1;i<=cnt;i++) dp[i]=INF;
priority_queue< pair<long long,int>,vector< pair<long long,int> >,greater< pair<long long,int> > > pq;
pq.push({dp[pos[1]]=0,pos[1]});
while(!pq.empty())
{
long long a=pq.top().first,b=pq.top().second;
pq.pop();
if(dp[b]<a) continue;
for(auto v:E[b]) if(dp[v.first]>a+v.second) pq.push({dp[v.first]=a+v.second,v.first});
}
if(dp[pos[n]]==INF) return cout<<-1,0;
cout<<dp[pos[n]];
}
