#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;
unordered_map<int,ll> sum[MAXN];
ll c[MAXN],p[MAXN];
V<pair<int,int>> adj[MAXN];
unordered_map<int,ll> 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});
sum[u][c[i]]+=p[i];
sum[v][c[i]]+=p[i];
}
dist[1][0]=0;
using iii=pair<ll,pair<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,d2]=pq.top();pq.pop();
auto [u,e]=d2;
if(get(u,e)!=d)continue;
for(auto [v,i]:adj[u]){if(i==e)continue;
ll ret=get(v,0),eq=sum[u][c[i]]-(e!=0&&c[i]==c[e]?p[e]:0);
if(ret>d+(eq-p[i])){
ret=d+(eq-p[i]);
dist[v][0]=ret;
pq.push({ret,{v,0}});
}
ll ret2=get(v,i);
if(ret2>d+p[i]){
ret2=d+p[i];
dist[v][i]=ret2;
pq.push({ret2,{v,i}});
}
}
}
ll ans=INF;
L(i,0,m){
ans=min(ans,get(n,i));
}
if(ans==INF)cout<<-1<<endl;
else cout<<ans<<endl;
}
