#include <bits/stdc++.h>
#define NMAX 100000
#define LOG 20
#define ll long long int
#define BASE 32
#define MOD 1000000007
using namespace std;
ifstream fin("cod.in");
ofstream fout("cod.out");
int n,m;
struct edge
{
int to,c,p,id;
};
struct state
{
ll d;
int x,t;
state(ll d,int x,int t)
{
this->d = d;
this->x = x;
this->t = t;
}
};
bool cmpHeap(state a,state b)
{
return a.d > b.d;
}
vector<edge> adj[NMAX+1];
set<int> bad[NMAX+1];
int rem[NMAX+1];
ll dist[NMAX+1][2];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin >> n >> m;
for(int i=1;i<=m;i++)
{
int a,b,c,p;
cin >> a >> b >> c >> p;
adj[a].push_back({b,c,p,i});
adj[b].push_back({a,c,p,i});
}
for(int i=1;i<=n;i++)
{
map<int,int> freq;
for(auto e : adj[i])
{
if(freq[e.c] > 0)
{
rem[i]++;
}
freq[e.c]++;
}
for(auto e : adj[i])
{
if(freq[e.c]>1)
{
bad[i].insert(e.id);
}
}
}
// for(int i=1;i<=n;i++)
// {
// dist[i][0] = dist[i][1] = 1e15;
// }
// vector<state> pq;
// dist[1][0] = 0;
// pq.push_back({0,1,0});
// while(!pq.empty())
// {
// push_heap(pq.begin(),pq.end(),cmpHeap);
// int x = pq.back().x;
// int t = pq.back().t;
// ll d = pq.back().d;
// pq.pop_back();
//
// if(d==dist[x][t])
// {
// int cost = rem[x] - t;
// for(auto e : adj[x])
// {
// int t1 = bad[e.to].find(e.id) != bad[e.to].end();
// if(dist[e.to][t1] > dist[x][t] + cost)
// {
// dist[e.to][t1] = dist[x][t] + cost;
// pq.push_back({dist[e.to][t1],e.to,t1});
// push_heap(pq.begin(),pq.end(),cmpHeap);
// }
// }
// }
// }
if(min(dist[n][0],dist[n][1])==1e15)
{
cout << -1;
}
else
{
cout << min(dist[n][0],dist[n][1]);
}
}
