#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;
};
pair<int,int> rid[NMAX+1];
map<pair<int,int>,int> idState;
ll dist[4*NMAX+1];
bool cmpHeap(pair<ll,int> a,pair<ll,int> b)
{
return a.first > b.first;
}
vector<edge> adj[NMAX+1];
map<int,int> bad[NMAX+1];
int main()
{
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});
}
rid[1] = {1,0};
idState[rid[1]]=1;
bad[1][0]=1;
for(int i=1;i<=n;i++)
{
for(auto e : adj[i])
{
if(idState.find({i,e.c})==idState.end())
{
idState[make_pair(i,e.c)] = idState.size() + 1;
rid[idState.size()] = {i,e.c};
}
bad[i][e.c]++;
}
}
for(int i=1;i<=idState.size();i++)
{
dist[i] = 1e9;
}
// vector<pair<ll,int>> pq;
// dist[1]=0;
// pq.push_back({0,1});
dist[1]=0;
deque<int> Q;
Q.push_back(1);
// while(!pq.empty())
// {
// pop_heap(pq.begin(),pq.end(),cmpHeap);
// int curr = pq.back().second;
// int x = rid[curr].first;
// int c = rid[curr].second;
// ll d = pq.back().first;
// pq.pop_back();
//
// if(dist[curr]==d)
// {
// for(auto e : adj[x])
// {
// int nxt = idState[{e.to,e.c}];
// int cost = bad[x][e.c]==1 ? 0 : c!=e.c;
// if(dist[nxt] > dist[curr] + cost)
// {
// dist[nxt] = dist[curr] + cost;
// pq.push_back({dist[nxt],nxt});
// push_heap(pq.begin(),pq.end(),cmpHeap);
// }
// }
// }
// }
while(!Q.empty())
{
int curr = Q.front();
int x = rid[curr].first;
int c = rid[curr].second;
Q.pop_front();
for(auto e : adj[x])
{
int cost = bad[x][e.c] == 1 ? 0 : (c!=e.c);
int nxt = idState[{e.to,e.c}];
if(dist[nxt] > dist[curr] + cost)
{
dist[nxt] = cost + 1;
if(cost == 1)
{
Q.push_back(nxt);
}
else
{
Q.push_front(nxt);
}
}
}
}
ll res = 1e9;
for(auto e : adj[n])
{
res=min(res,dist[idState[{n,e.c}]]);
}
if(res==1e9)
{
cout << -1;
}
else
{
cout << res;
}
}
