#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fs first
#define sc second
#define pb push_back
void solve() {
int n,m;
cin>>n>>m;
vector<pair<pii,pii>> ed;
map<int,vector<int>> vc[n+1];
for(int i=0;i<m;i++){
int x,y,c,p;
cin>>x>>y>>c>>p;
ed.pb({{x,y},{c,p}});
ed.pb({{y,x},{c,p}});
vc[x][c].pb(y);
vc[y][c].pb(x);
}
sort(ed.begin(),ed.end());
auto gid=[&](int x,int y){
pair<pii,pii> p={{x,y},{0,0}};
return lower_bound(ed.begin(),ed.end(),p)-ed.begin();
};
int k=ed.size();
vector<pll> ad[k+n];
for(int i=1;i<=n;i++){
int cn=k+i-1;
for(auto[c,v]:vc[i]){
for(int j:v){
ad[gid(i,j)].pb({cn,0});
int t=gid(j,i);
ad[cn].pb({t,ed[t].sc.sc});
}
if(v.size()==1){
ad[cn].pb({k+v[0]-1,0});
}else if(v.size()==2){
ad[gid(i,v[0])].pb({k+v[1]-1,0});
ad[gid(i,v[1])].pb({k+v[0]-1,0});
}
}
}
ll ds[k+n];
bool vs[k+n];
memset(ds,63,sizeof(ds));
memset(vs,0,sizeof(vs));
priority_queue<pll> pq;
pq.push({k,0});
ds[k]=0;
while(!pq.empty()){
int v=pq.top().sc;
pq.pop();
if(vs[v])continue;
vs[v]=1;
if(v==n+k-1){
cout<<ds[v]<<'\n';
return;
}
for(auto[u,w]:ad[v])if(!vs[u]){
ds[u]=min(ds[u],ds[v]+w);
pq.push({-ds[u],u});
}
}
cout<<"-1\n";
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
solve();
}
