#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];
map<int,ll> sm[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);
sm[x][c]+=p;
sm[y][c]+=p;
}
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();
};
vector<pii> nc;
for(int i=1;i<=n;i++){
for(auto[c,s]:sm[i]){
nc.pb({i,c});
}
}
auto gid2=[&](int x,int y){
pii p={x,y};
return lower_bound(nc.begin(),nc.end(),p)-nc.begin();
};
int k=ed.size(),k2=nc.size();
vector<pll> ad[k+n+k2];
for(int i=1;i<=n;i++){
int cn=k+i-1;
for(auto[c,v]:vc[i]){
ll s=sm[i][c];
for(int j:v){
ad[gid(i,j)].pb({cn,0});
int t=gid(j,i);
ll p=ed[t].sc.sc;
ad[cn].pb({t,min(p,s-p)});
}
int cc=k+n+gid2(i,c);
for(int j:v){
int z=gid(i,j);
ll p=ed[z].sc.sc;
ad[z].pb({cc,-p});
ad[cc].pb({k+j-1,s-p});
}
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+k2];
bool vs[k+n+k2];
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();
}
