#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=2e5+5;
const ll inf=2e18;
int n,m;
ll d[maxN+1];
struct duongdi
{
int u;
ll w;
bool operator < (const duongdi &o)const
{
return w>o.w;
}
};
priority_queue<duongdi> pq;
struct col
{
int u,c;
ll p;
};
vector<col> adj[maxN+1];
ll color[maxN+1];
unordered_map<int,ll> mp[maxN+1];
int main()
{
//freopen("","r",stdin);
//freopen("","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v,c;
ll p;
cin>>u>>v>>c>>p;
adj[u].push_back({v,c,p});
adj[v].push_back({u,c,p});
mp[u][c]+=p;
mp[v][c]+=p;
}
for(int i=1;i<=n;i++)
{
d[i]=inf;
}
d[1]=0;
pq.push({1,0});
while(!pq.empty())
{
duongdi tmp=pq.top();
pq.pop();
int u=tmp.u;
ll w=tmp.w;
if(d[u]<w)
{
continue;
}
for(auto i:adj[u])
{
color[i.c]=inf;
}
for(auto i:adj[u])
{
int v=i.u;
ll tmp=mp[u][i.c]-i.p;
color[i.c]=min(color[i.c],d[v]);
if(d[v]>d[u]+tmp)
{
d[v]=d[u]+tmp;
pq.push({v,d[v]});
}
if(d[v]>d[u]+i.p)
{
d[v]=d[u]+i.p;
pq.push({v,d[v]});
}
}
for(auto i:adj[u])
{
int v=i.u;
ll tmp=mp[u][i.c]-i.p;
if(d[v]>color[i.c]+tmp)
{
d[v]=color[i.c]+tmp;
//cout<<v<<" "<<u<<" "<<mn<<" "<<tmp<<" "<<d[v]<<'\n';
pq.push({v,d[v]});
}
}
}
if(d[n]==inf)
{
cout<<-1;
}
else cout<<d[n];
}
