#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][2];
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][0].resize(ma[i].size()+2,1e18);
dp[i][1].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(int i=0;i<ma[1].size();i++)
{
dp[1][0][i]=0;
pq.push({0,1,0,i});
}
while(pq.size()>0)
{
auto it=pq.top();
pq.pop();
int x=it[1],j=it[3],dt=it[0],chg=it[2];
if(dt!=dp[x][chg][j])
{
continue;
}
// // O(M)
// // last used
int uid=ma[x][j].second,col=ma[x][j].first;
if(chg)
{
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]);
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(nc<dp[oth][1][idp])
{
dp[oth][1][idp]=nc; // change this edge or change all other with same color
pq.push({nc,oth,1,idp});
}
nc=min(sm[x][c]-p[id]-p[uid]*(col==c),p[id])+dt;
if(nc<dp[oth][0][idp])
{
dp[oth][0][idp]=nc; // change this edge or change all other with same color
pq.push({nc,oth,0,idp});
}
pair<int,int> ftp,stp;
ftp.first=c;
ftp.second=m;
stp.first=c;
stp.second=1;
int cnp=upper_bound(begin(ma[x]),end(ma[x]),ftp)-lower_bound(begin(ma[x]),end(ma[x]),stp);
nc=dt;
if((cnp==1 or (cnp==2 and c==col)) and nc<dp[oth][0][idp])
{
dp[oth][0][idp]=nc;
pq.push({nc,oth,0,idp});
}
}
}
else{
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]);
int nc=min(sm[x][c]+sm[oth][c]-2*p[id],p[id])+dt;
if(nc<dp[oth][1][idp])
{
dp[oth][1][idp]=nc; // change this edge or change all other with same color
pq.push({nc,oth,1,idp});
}
nc=min(sm[x][c]-p[id],p[id])+dt;
if(nc<dp[oth][0][idp])
{
dp[oth][0][idp]=nc; // change this edge or change all other with same color
pq.push({nc,oth,0,idp});
}
pair<int,int> ftp,stp;
ftp.first=c;
ftp.second=m;
stp.first=c;
stp.second=1;
int cnp=upper_bound(begin(ma[x]),end(ma[x]),ftp)-lower_bound(begin(ma[x]),end(ma[x]),stp);
nc=dt;
if(cnp==1 and nc<dp[oth][0][idp])
{
dp[oth][0][idp]=nc;
pq.push({nc,oth,0,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][0][j]);
for(int j=0;j<ma[x].size();j++)ans=min(ans,dp[x][1][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;
}
