#include <bits/stdc++.h>
#define V vector
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define all(x) x.begin(),x.end()
#define sz(a) ((int)a.size())
#define pb push_back
using namespace std;
typedef long long ll;
//Si tengo un nodo, tengo dos opciones, hacer la arista i "única"
//Hacer el color C único en el nodo v
const int MAXN=2e5+5;
const ll INF=1e18;
ll c[MAXN],p[MAXN];
V<pair<int,int>> adj[MAXN];
unordered_map<int,V<pair<int,int>>>adjc[MAXN];
unordered_map<int,ll> sum[MAXN],dist[MAXN];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;cin>>n>>m;
L(i,1,m){
int u,v;cin>>u>>v;
cin>>c[i]>>p[i];
adj[u].pb({v,i});
adj[v].pb({u,i});
adjc[u][c[i]].pb({v,i});
adjc[v][c[i]].pb({u,i});
sum[u][c[i]]+=p[i];
sum[v][c[i]]+=p[i];
}
dist[1][0]=0;
using iii=tuple<ll,ll,ll>;
priority_queue<iii,vector<iii>,greater<iii>>pq;
pq.push({0,1,0});
auto get=[&](int a,int b)->ll{
if(dist[a].find(b)!=end(dist[a])){
return dist[a][b];
}else return INF;
};
while(sz(pq)){
auto [d,u,ty]=pq.top();pq.pop();
if(get(u,ty)!=d)continue;
if(ty==0){
for(auto [v,i]:adj[u]){
int add=min(p[i],sum[u][c[i]]-p[i]);
if(get(v,0)>d+add){
dist[v][0]=d+add;
pq.push({dist[v][0],v,0});
}
if(get(v,c[i])>d){
dist[v][c[i]]=d;
pq.push({dist[v][c[i]],v,c[i]});
}
}
}else{
for(auto [v,i]:adjc[u][ty]){
if(get(v,0)>d+(sum[u][ty]-p[i])){
dist[v][0]=d+(sum[u][ty]-p[i]);
pq.push({dist[v][0],v,0});
}
}
}
}
ll ans=get(n,0);
if(ans==INF)cout<<-1<<endl;
else cout<<ans<<endl;
}
