#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define se second
#define X first
#define Y second
#define ist insert
#define pii pair<int,int>
typedef long long ll;
using namespace std;
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
const int INF=170000000000000;//2147483647;
const int MOD=998244353;//1000000007;
const int N=100005;
struct I{
int u,c,p;
};
int n,m;
vector<I> e[N];
int d[N];
priority_queue<pii,vector<pii>,greater<pii>> pq;
map<int,int> mp[N];
void dij(){
fill(d,d+N,INF);
d[1]=0;
pq.push({0,1});
while (pq.size()){
auto [w,v]=pq.top();pq.pop();
if (d[v]<w) continue;
for (auto [u,c,p]:e[v]){
if (d[u]>(mp[v][c]-1)+w){
d[u]=(mp[v][c]-1)+w;
pq.push({d[u],u});
}
}
}
if (d[n]==INF) cout <<-1;
else cout <<d[n];
}
void sol(){
cin >>n>>m;
for (int i=0,u,v,c,p;i<m;i++){
cin >>u>>v>>c>>p;
e[u].pb({v,c,p});
e[v].pb({u,c,p});
mp[u][c]++;
mp[v][c]++;
}
dij();
}
signed main()
{
int _=1;
//cin >>_;
while (_--) sol();
return 0;
}
