#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
const int inf=1e18;
struct freq
{
int x,time;
};
struct elem
{
int x,col,cost;
bool operator<(const elem& e) const
{
return cost<e.cost;
}
};
freq f[N];
int n,m,i,j,x,y,c,p,d[N];
vector<elem> edge[N],one[N],two[N],more[N];
void dijkstra(int orig)
{
for(i=1;i<=n;++i)
d[i]=inf;
priority_queue<elem> q;
q.push({orig,0,0});
d[orig]=0;
while(!q.empty())
{
auto e=q.top();
q.pop();
int x=e.x,curr_col=e.col;
for(auto f:one[x])
{
int y=f.x,col=f.col,cost=f.cost;
if(d[y]>d[x])
{
d[y]=d[x];
q.push({y,col,d[y]});
}
}
for(auto f:two[x])
{
int y=f.x,col=f.col,cost=f.cost;
if(curr_col==col) cost=0;
if(d[y]>d[x]+cost)
{
d[y]=d[x]+cost;
q.push({y,col,d[y]});
}
}
for(auto f:more[x])
{
int y=f.x,col=f.col,cost=f.cost;
if(d[y]>d[x]+cost)
{
d[y]=d[x]+cost;
q.push({y,col,d[y]});
}
}
}
}
signed main()
{
cin>>n>>m;
for(i=1;i<=m;++i)
{
cin>>x>>y>>c>>p;
edge[x].push_back({y,c,p});
}
for(i=1;i<=n;++i)
{
for(auto e:edge[i])
{
int x=e.x,c=e.col;
if(f[c].time!=i)
{
f[c].time=i;
f[c].x=1;
}
else
f[c].x++;
}
for(auto e:edge[i])
{
int x=e.x,col=e.col,cost=e.cost;
if(f[col].x==1) one[i].push_back({x,col,cost});
else if(f[col].x==2) two[i].push_back({x,col,cost});
else more[i].push_back({x,col,cost});
}
}
dijkstra(1);
if(d[n]==inf) cout<<-1;
else cout<<d[n];
return 0;
}
