#include <bits/stdc++.h>
#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 1e5+5, M = 2e5 + 5;
struct edge {
int v, c, p;
};
int dis[N], cnt[M];
vector<edge> adj[N];
signed main() {
fastio
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, c, p;
cin >> u >> v >> c >> p;
adj[u].push_back({v, c, p});
adj[v].push_back({u, c, p});
}
fill(dis,dis+N,1e18);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
dis[1] = 0;
pq.push({0, 1});
//dis, vertex, lst
while (!pq.empty()) {
auto [ww, u] = pq.top();
pq.pop();
if (ww > dis[u])
continue;
for (auto [v, c, p] : adj[u]) {
cnt[c]++;
}
for (auto [v, c, p] : adj[u]) {
if (dis[v] > dis[u] + (cnt[c] == 1 ? 0 : 1)) {
dis[v] = dis[u] + (cnt[c] == 1 ? 0 : 1);
pq.push({dis[v], v});
}
}
for (auto [v, c, p] : adj[u]) {
cnt[c]--;
}
}
int ans = 1e18;
ans = min(ans,dis[n]);
cout << (ans == 1e18 ? -1 : ans) << "\n";
}
