#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Forr(i,a,b) for(int i=a;i>=b;i--)
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define INF (1000000000000000ll);
#define int ll
using namespace std;
using ll=long long;
using pii=pair<int,int>;
struct Edge{
int id,col,pri;
};
vector<Edge> ed;
vector<int> adj[1010];
map<int,int> cnt[1010];
map<int,int> dist[1010];
int32_t main(){
ios::sync_with_stdio(false);
cin.tie(0);
// nachoneko sama & miku sama bless me >/////<
int n,m; cin>>n>>m;
For(i,1,m){
int a,b,c,p; cin>>a>>b>>c>>p;
adj[a].eb(sz(ed));
adj[b].eb(sz(ed));
cnt[a][c]++;
cnt[b][c]++;
ed.push_back({a^b,c,p});
}
using pip=pair<int,pii>;
priority_queue<pip,vector<pip>,greater<pip>> pq;
pq.emplace(0,pii(0,1));
while(!pq.empty()){
int d=pq.top().F;
int lcol=pq.top().S.F;
int now=pq.top().S.S;
pq.pop();
if(now==n){
cout<<d<<"\n";
exit(0);
}
if(dist[now].count(lcol)) continue;
dist[now][lcol]=d;
for(auto &eid:adj[now]){
auto &e=ed[eid];
int to=e.id^now;
if(to==1) continue;
int count=cnt[now][e.col];
if(!dist[to].count(e.col))
pq.emplace(d+((count-(e.col==lcol))>1),pii(e.col,to));
}
}
cout<<"-1\n";
return 0;
}
