#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=1e5+5;
ll n, m, u, v, c, p, mn=1e18, cnt;
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], dp[nx][2];
ll getval(ll idx, ll c, ll t)
{
if (dp[idx][t].find(c)==dp[idx][t].end()) return 1e18;
return dp[idx][t][c];
}
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]++;
dp[1][0][-1]=0;
pq.push({0, 1, -1, 0});
while (!pq.empty())
{
auto [cst, u, p, t]=pq.top();
pq.pop();
//cout<<"debug "<<cst<<' '<<u<<' '<<p<<' '<<t<<'\n';
for (auto [v, c]:d[u])
{
if (mp[u][c]>2||((mp[u][c]==2)&&p!=c))
{
if (cst+1<getval(v, c, 1)) dp[v][1][c]=cst+1, pq.push({cst+1, v, c, 1});
}
else if (mp[u][c]==2&&p==c)
{
if (t==1)
{
if (cst<getval(v, c, 0)) dp[v][0][c]=cst, pq.push({cst, v, c, 0});
}
else
{
if (cst+1<getval(v, c, 1)) dp[v][1][c]=cst+1, pq.push({cst+1, v, c, 1});
}
}
else
{
if (cst<getval(v, c, 0)) dp[v][0][c]=cst, pq.push({cst, v, c, 0});
}
}
}
for (auto x:dp[n][0]) mn=min(mn, x.second);
for (auto x:dp[n][0]) mn=min(mn, x.second);
if (mn==1e18) cout<<-1;
else cout<<mn;
}
