#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define p(x,y) pair<ll,ll>(x,y)
#define BIT(i,x) ((x>>i)&1)
#define MASK(x) (1<<x)
#define ld long double
#define __builtin_popcount __builtin_popcountll
#define pll pair<ll,ll>
template<class T1,class T2>
bool maximize(T1 &x,const T2 &y)
{
if(x<y)
{
x=y;
return 1;
}
return 0;
}
template<class T1,class T2>
bool minimize(T1 &x,const T2 &y)
{
if(x>y)
{
x=y;
return 1;
}
return 0;
}
void online()
{
std::ios_base::sync_with_stdio(0);
cin.tie(0);
#ifdef thuc
freopen("input.INP","r",stdin);
freopen("output.OUT","w",stdout);
#endif
}
const ll N=2e5+10,inf=1e18;
map<ll,vector<pll> > gr[N];
map<ll,ll> f1[N],sum[N],vs[N];
ll f[N];
ll n,m;
struct info
{
ll d,u,s;
info(ll _d=0,ll _u=0,ll _s=0)
{
d=_d;
u=_u;
s=_s;
}
bool operator <(const info &o) const
{
return d>o.d;
}
};
int main()
{
online();
cin>>n>>m;
for(int i=1; i<=m; i++)
{
ll u,v,c,s;
cin>>u>>v>>c>>s;
gr[u][c].emplace_back(v,s);
gr[v][c].emplace_back(u,s);
sum[u][c]+=s;
sum[v][c]+=s;
}
priority_queue<info> qq;
memset(f,0x3f,sizeof f);
f[1]=0;
qq.emplace(0,1,0);
while(qq.size())
{
auto [d,u,s]=qq.top();
qq.pop();
if(!s)
{
if(d!=f[u]) continue;
for(auto &[c,adj]:gr[u])
{
for(auto [v,w]:adj)
{
if(minimize(f[v],f[u]+sum[u][c]-w))
{
qq.emplace(f[v],v,0);
}
if(minimize(f[v],f[u]+w))
{
qq.emplace(f[v],v,0);
}
if(vs[v][c]==0||minimize(f1[v][c],f[u]))
{
vs[v][c]=1;
f1[v][c]=f[u];
qq.emplace(f1[v][c],v,c);
}
}
}
}
else
{
if(d!=f1[u][s]) continue;
ll c=s;
for(auto [v,w]:gr[u][s])
{
if(minimize(f[v],f1[u][s]+sum[u][c]-w))
{
qq.emplace(f[v],v,0);
}
}
}
}
if(f[n]>1e18) f[n]=-1;
cout<<f[n];
}
