#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];
}
}
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});
}
}
}
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});
}
}
// }
}
}
ll ans=1e18;
for(int j=0;j<ma[n].size();j++)ans=min(ans,dp[n][0][j]);
for(int j=0;j<ma[n].size();j++)ans=min(ans,dp[n][1][j]);
if(ans==1e18)ans=-1;
cout<<ans<<endl;
}
