#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(),v.end()
#define eb push_back
#define ll long long
#define fi first
#define se second
int t,n,i,u,v,c,m;
ll w;
const int maxn = 1e5 + 10;
const ll inf = 1e16;
struct edge
{
int to,c;
ll w;
bool operator < (const edge &b)const
{
if(w != b.w)return w > b.w;
return to > b.to;
}
};
map<int,vector<edge>>adj[maxn];
map<int,ll> sum[maxn];
ll d[maxn];
map<int,ll> pass[maxn];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
while(m--)
{
cin>>u>>v>>c>>w;
adj[u][c].eb({v,c,w});
adj[v][c].eb({u,c,w});
sum[u][c] += w;
sum[v][c] += w;
}
priority_queue<edge>q;
q.push({1,0,0});
for(i = 2;i<=n;i++)d[i] = inf;
while(q.size())
{
i = q.top().to;
w = q.top().w;
c = q.top().c;
q.pop();
if(c)
{
if(pass[i][c] != w)continue;
for(auto k : adj[i][c])
{
ll tmp = sum[i][c] - k.w;
if(d[k.to] > tmp + w )
{
d[k.to] = tmp + w;
q.push({k.to,0,d[k.to]});
}
}
}
else
{
if(d[i] != w)continue;
for(auto j : adj[i])
{
for(auto k : j.se)
{
ll tmp = sum[i][k.c] - k.w;
if(d[k.to] > tmp + w)
{
d[k.to] = tmp + w;
q.push({k.to,0,d[k.to]});
}
if(d[k.to] > k.w + w)
{
d[k.to] = k.w + w;
q.push({k.to,0,d[k.to]});
}
if(pass[k.to].find(k.c) == pass[k.to].end() || pass[k.to][k.c] > w)
{
pass[k.to][k.c] = w;
q.push({k.to,k.c,w});
}
}
}
}
}
if(d[n] >= inf)d[n] =-1;
cout<<d[n];
return 0;
}
