#include <bits/stdc++.h>
#define pb push_back
#define sp " "
#define sl "\n"
#define fi first
#define se second
#define mp make_pair
#define sz(a) ((int)a.size())
#define all(a) a.begin(),a.end()
#define rev(a) reverse(a.begin(),a.end())
#define PI 3.141592
#define fo(i,n) for (int i=0;i<n;i++)
#define fofo(i,n,j,m) for (int i=0;i<n;i++) for (int j=0;j<m;j++)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
const int N=1e5+5,M=2e5+5,mod=1e9+7;
ll n,m;
map<ll,ll> h[N];
map<ll,ll> hp[N];
vector<ll> g[N];
map<ii,ll> pr;
map<ii,ll> co;
bool vs[N];
map<ll,vector<ll>> back[N];
ll res[N];
priority_queue<ii,vector<ii>,greater<ii>> pq;
void dij(ll cost,ll node)
{
if (vs[node]) return;
vs[node] = true;
res[node] = cost;
//cout << node << " "<< res[node] << "\n";
for (int u : g[node]) {
int colorcito = co[{node,u}];
if (!vs[u]) if ( h[node][colorcito]==1) {
pq.push({cost,u});
//dij(u,cost);
///cout << node << " " << u << "\n";
}
}
for (int u : g[node]) {
int colorcito = co[{node,u}];
ll precioo = pr[{node,u}];
if (!vs[u]) if (h[node][colorcito]>1) {
pq.push({cost+1,u});
/// cout << node << " " << u << "\n";
//dij(u,cost);
}
}
}
int main() {
cin.tie(0); cout.tie(0);
ios_base::sync_with_stdio();
cin >> n >> m;
for (int i=0;i<m;i++) {
ll a,b,c,p;
cin >> a >> b >> c >> p;
co[{a,b}] = c;
co[{b,a}] = c;
pr[{a,b}] = p;
pr[{b,a}] = p;
g[a].push_back(b);
g[b].push_back(a);
back[a][c].push_back(b);
back[b][c].push_back(a);
h[a][c]++;
hp[a][c] += p;
h[b][c]++;
hp[b][c] += p;
}
pq.push({0,1});
while (!pq.empty()) {
auto x = pq.top();
pq.pop();
dij(x.fi,x.se);
}
if (!vs[n]) cout << -1;
else cout << res[n];
return 0;
}
// Recuerda limites
// Recuerda casos especiales
