#include <bits/stdc++.h>
#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i<b; i++)
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cout.tie(0); cin.tie(0);
using namespace std;
typedef long long ll;
const int MAXN = 2000000;
ll n,m;
struct Arista{
ll u;
ll v;
ll c;
ll w;
};
vector<Arista> e[MAXN];
vector<pair<ll,ll>> adj[MAXN];
map<ll,ll> sum[MAXN];
map<ll,ll> nind[MAXN];
ll u[MAXN];
ll v[MAXN];
ll c[MAXN];
ll w[MAXN];
ll dist[MAXN];
int main(){
forn(i,0,MAXN) dist[i]=2000000000000;
cin>>n>>m;
forn(i,0,m){
cin>>u[i]>>v[i]>>c[i]>>w[i]; u[i]--; v[i]--;
sum[u[i]][c[i]]+=w[i];
sum[v[i]][c[i]]+=w[i];
e[u[i]].pb({u[i],v[i],c[i],w[i]});
e[v[i]].pb({v[i],u[i],c[i],w[i]});
}
ll next = n + 5;
forn(i,0,n){
for(auto ari:e[i]){
ll j = ari.v;
ll nc = ari.c;
ll nw = ari.w;
ll &ind = nind[j][nc];
if(ind==0) ind=next, next++;
adj[i].pb({ind,0});
adj[ind].pb({i, sum[j][nc]-nw});
adj[i].pb({j,nw});
adj[i].pb({j,sum[i][nc]-nw});
}
}
dist[0]=0;
priority_queue<pair<ll,ll>> pq; pq.push({0,0});
while(!pq.empty()){
ll nd = pq.top().snd;
ll cost = pq.top().fst*-1;
pq.pop();
if(dist[nd]!=cost) continue;
for(auto i:adj[nd]){
if(dist[i.fst]>cost+i.snd){
dist[i.fst]=cost+i.snd;
pq.push({dist[i.fst]*-1,i.fst});
}
}
}
if(dist[n-1]==2000000000000) cout<<-1<<'\n';
else cout<<dist[n-1]<<'\n';
return 0;
}
