#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=1e5+5;
ll n, m, u, v, c, p, dp[nx][2];
priority_queue<tuple<ll, ll, ll, ll>, vector<tuple<ll, ll, ll, ll>>, greater<tuple<ll, ll, ll, ll>>> pq;
vector<pair<ll, ll>> d[nx];
map<ll, ll> mp[nx];
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>m;
for (int i=1; i<=m; i++) cin>>u>>v>>c>>p, d[u].push_back({v, c}), d[v].push_back({u, c}), mp[u][c]++, mp[v][c]++;
for (int i=1; i<=n; i++) dp[i][0]=dp[i][1]=1e18;
dp[1][0]=0;
pq.push({0, 1, -1, 0});
while (!pq.empty())
{
auto [cst, u, p, t]=pq.top();
pq.pop();
for (auto [v, c]:d[u])
{
if (mp[u][c]>2||((mp[u][c]==2)&&p!=c))
{
if (cst+1<dp[v][1]) dp[v][1]=cst+1, pq.push({cst+1, v, c, 1});
}
else if (mp[u][c]==2&&p==c)
{
if (cst+(t!=1)<dp[v][1]) dp[v][1]=cst+(t!=1), pq.push({cst+(t!=1), v, c, 1});
}
else
{
if (cst<dp[v][0]) dp[v][0]=cst, pq.push({cst, v, c, 0});
}
}
}
if (min(dp[n][0], dp[n][1])==1e18) cout<<-1;
else cout<<min(dp[n][0], dp[n][1]);
}
