#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> llll;
const ll INF=1e18;
const int N=1e5+5;
struct edge
{
int v,c;
ll p;
};
map<int,vector<edge>> graph[N];
ll dp[N];
map<int,ll> dp1[N],ps[N];
void solve()
{
int n,m;
cin >> n >> m;
for(int i=1;i<=m;i++)
{
int u,v,c;
ll p;
cin >> u >> v >> c >> p;
graph[u][c].push_back({v,c,p});
graph[v][c].push_back({u,c,p});
ps[u][c]+=p;
ps[v][c]+=p;
}
for(int i=1;i<=n;i++) dp[i]=INF;
dp[1]=0;
priority_queue<pair<ll,pii>,vector<pair<ll,pii>>,greater<pair<ll,pii>>> pq;
pq.push({0,{1,0}});
while((int)pq.size())
{
ll temp=pq.top().fi;
int u=pq.top().se.fi,c=pq.top().se.se;
pq.pop();
if(c)
{
if(dp1[u][c]!=temp) continue;
for(int i=0;i<(int)graph[u][c].size();i++)
{
edge e=graph[u][c][i];
ll w1=ps[u][c]-e.p;
if(dp1[u][c]+w1<dp[e.v])
{
dp[e.v]=w1+dp1[u][c];
pq.push({dp[e.v],{e.v,0}});
}
}
}
else
{
if(dp[u]!=temp) continue;
for(map<int,vector<edge>>::iterator it=graph[u].begin();it!=graph[u].end();it++)
{
for(int i=0;i<(int)it->se.size();i++)
{
edge e=it->se[i];
ll w1=ps[u][e.c]-e.p;
if(dp[u]+w1<dp[e.v])
{
dp[e.v]=dp[u]+w1;
pq.push({dp[e.v],{e.v,0}});
}
ll w2=e.p;
if(dp[u]+w2<dp[e.v])
{
dp[e.v]=dp[u]+w2;
pq.push({dp[e.v],{e.v,0}});
}
if(!dp1[e.v].count(e.c)||dp[u]<dp1[e.v][e.c])
{
dp1[e.v][e.c]=dp[u];
pq.push({dp1[e.v][e.c],{e.v,e.c}});
}
}
}
}
}
if(dp[n]>=INF) dp[n]=-1;
cout << dp[n] << endl;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("hanhhhh.inp","r",stdin);
//freopen("hanhhhh.out","w",stdout);
int t=1;
//cin >> t;
while(t--)
solve();
return 0;
}
