#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define ii pair<int,int>
#define lll pair<ll,ll>
#define vi vector<int>
#define vvi vector<vector<int>>
struct P{
ll v,c,w;
};
vector<P>a[1000001];
map<ll,ll>mp[1000001];
ll d[1000001];
int n,m;
void djk()
{
priority_queue<lll>q;
q.push({0,1});
d[1]=0;
for(int i=2;i<=n;i++){
d[i]=1e18;
}
while(q.size()){
ll u=q.top().second,wu=-q.top().first;
q.pop();
for(P it:a[u]){
ll v=it.v,c=it.c,w=it.w;
if(mp[u][c]==1){
if(wu<d[v]){
d[v]=wu;
q.push({-wu,v});
}
}else{
if(wu+1LL*w<d[v]){
d[v]=wu+1LL*w;
q.push({-(wu+1LL*w),v});
}
}
}
}
if(d[n]==1e18)cout<<-1;
else cout<<d[n];
}
void sc()
{
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,c,w;cin>>u>>v>>c>>w;
a[u].push_back({v,c,w});
a[v].push_back({u,c,w});
mp[u][c]+=1;
mp[v][c]+=1;
}
djk();
}
int main()
{
// freopen("robot1.inp","w",stdout);
//freopen("robot1.out","w",stdout);
ios_base :: sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
sc() ;
return 0 ; ///sc
}
