#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define f first
#define s second
using namespace std;
ll n, m, x, y, c, p;
vector<pll> v[100001];
unordered_map<ll, ll> cnt[100001], dist[100001];
priority_queue<pair<pll, ll>, vector<pair<pll, ll> >, greater<pair<pll, ll> > > pq;
void dij(ll st){
for (pll i: v[st]){
dist[st][i.s]=0;
pq.push({{0, st}, i.s});
}
while (!pq.empty()){
pll p=pq.top().f;
ll color=pq.top().s;
pq.pop();
if (dist[p.s][abs(color)]!=p.f) continue;
if (color<0) cnt[p.s][-color]--;
for (pll i: v[p.s]){
if (cnt[p.s][i.s]==1){
if (dist[i.f][i.s]>p.f){
dist[i.f][i.s]=p.f;
pq.push({{p.f, i.f}, i.s});
}
}else{
if (dist[i.f][i.s]>p.f+1){
dist[i.f][i.s]=p.f+1;
pq.push({{p.f+1, i.f}, -i.s});
}
}
}
if (color<0) cnt[p.s][-color]++;
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i=1; i<=m; i++){
cin >> x >> y >> c >> p;
v[x].push_back({y, c});
v[y].push_back({x, c});
cnt[x][c]++, cnt[y][c]++;
dist[x][c]=dist[y][c]=1e18;
}
dij(1);
ll ans=1e18;
for (pll i: v[n]) ans=min(ans, dist[n][i.s]);
if (ans==1e18) cout << "-1\n";
else cout << ans << "\n";
}
