#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
const int N=2e5+100;
int a[N],b[N],c[N],p[N];
vector<pair<int,int>> ma[N];
vector<ll> dp[N];
map<int,ll> sm[N];
bool vis[N];
int32_t 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++)
{
cin>>a[i]>>b[i]>>c[i]>>p[i];
ma[a[i]].push_back({c[i],i});
ma[b[i]].push_back({c[i],i});
}
for(int i=1;i<=n;i++)
{
sort(begin(ma[i]),end(ma[i]));
dp[i].resize(ma[i].size()+2,1e18);
for(auto tlx:ma[i])
{
sm[i][tlx.first]+=p[tlx.second];
// if(i==5)
// {
// cout<<"For five "<<tlx.first<<' '<<tlx.second<<' '<<p[tlx.second]<<' '<<sm[i][tlx.first]<<endl;
// }
// if(i==7)
// {
// cout<<"For seven "<<tlx.first<<' '<<tlx.second<<' '<<p[tlx.second]<<' '<<sm[i][tlx.first]<<endl;
// }
}
}
priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>>pq;
for(auto tlx:ma[1])
{
int c=tlx.first,id=tlx.second;
int oth=a[id]+b[id]-1,idp=lower_bound(begin(ma[oth]),end(ma[oth]),tlx)-begin(ma[oth]);
dp[oth][idp]=min(dp[oth][idp],min(sm[1][c]+sm[oth][c]-2*p[id],p[id])); // change this edge or change all other with same color
pq.push({dp[oth][idp],oth,idp});
}
// cout<<"DEG "<<ma[5].size()<<endl;
while(pq.size()>0)
{
auto it=pq.top();
pq.pop();
int x=it[1],j=it[2],dt=it[0];
if(dt!=dp[x][j])
{
continue;
}
// // O(M)
// // last used
int uid=ma[x][j].second,col=ma[x][j].first;
for(int tlx=0;tlx<ma[x].size();tlx++)
{
if(tlx==j)continue;
int c=ma[x][tlx].first,id=ma[x][tlx].second;
int oth=a[id]+b[id]-x,idp=lower_bound(begin(ma[oth]),end(ma[oth]),ma[x][tlx])-begin(ma[oth]);
// if oth==n there is a little bit change in the update
bool ed=(oth==n);
int f=1;
auto txp=lower_bound(begin(ma[oth]),end(ma[oth]),ma[x][j]);
if(txp!=end(ma[oth]) and (*txp)==ma[x][j])f++;
int nc=min(sm[x][c]+sm[oth][c]-2*p[id]-f*p[uid]*(col==c),p[id])+dt;
// if(ed)
// {
// cout<<"From "<<x<<' '<<j<<' '<<dt<<" bef "<<nc<<" af ";
// nc=min(nc,dt+min(sm[x][c]-p[id]-p[uid]*(col==c),p[id]));
// cout<<nc<<endl;
// }
// cout<<"From "<<x<<' '<<j<<' '<<dt<<" To "<<oth<<' '<<idp<<' '<<nc<<endl;
if(nc<dp[oth][idp])
{
// if(nc<=0)
// {
// cout<<"Hola "<<x<<' '<<j<<' '<<dt<<endl;
// // cout<<c<<' '<<id<<' '<<oth<<' '<<idp<<' '<<f<<' '<<nc<<endl;
// // cout<<ma[oth].size()<<' '<<ma[oth][idp].first<<' '<<ma[oth][idp].second<<endl;;
// cout<<sm[x][c]<<' '<<sm[oth][c]<<endl;
// cout<<id<<' '<<p[id]<<' '<<uid<<' '<<p[uid]<<' '<<col<<' '<<c<<endl;;
// return 0;
// }
dp[oth][idp]=nc; // change this edge or change all other with same color
pq.push({nc,oth,idp});
}
}
}
// start from n and take edge only if count of that color from the other side of edge is one
queue<int> q;
ll ans=1e18;
q.push(n);
while(q.size())
{
int x=q.front();
vis[x]=1;
q.pop();
for(int j=0;j<ma[x].size();j++)ans=min(ans,dp[x][j]);
for(int tlx=0;tlx<ma[x].size();tlx++)
{
int c=ma[x][tlx].first,id=ma[x][tlx].second;
int oth=a[id]+b[id]-x;
// int cnp=0;
pair<int,int> ftp,stp;
ftp.first=c;
ftp.second=m;
stp.first=c;
stp.second=1;
int cnp=upper_bound(begin(ma[oth]),end(ma[oth]),ftp)-lower_bound(begin(ma[oth]),end(ma[oth]),stp);
if(cnp==1 and !vis[oth])
{
vis[oth]=1;
q.push(oth);
}
}
}
if(ans==1e18)ans=-1;
cout<<ans<<endl;
}
