#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;
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]=20000000000000000;
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];
}
ll next = n+5;
forn(i,0,m){
ll &ind = nind[v[i]][c[i]];
if(ind==0) ind=next, next++;
adj[u[i]].pb({ind,0});
adj[ind].pb({u[i],sum[v[i]][c[i]]-w[i]});
ll &ind2 = nind[u[i]][c[i]];
if(ind2==0) ind2=next, next++;
adj[v[i]].pb({ind2,0});
adj[ind2].pb({v[i],sum[u[i]][c[i]]-w[i]});
adj[u[i]].pb({v[i],w[i]});
adj[u[i]].pb({v[i],sum[u[i]][c[i]]-w[i]});
adj[v[i]].pb({u[i],w[i]});
adj[v[i]].pb({u[i],sum[v[i]][c[i]]-w[i]});
}
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]==20000000000000000) cout<<-1<<'\n';
else cout<<dist[n-1]<<'\n';
return 0;
}
