#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Forr(i,a,b) for(int i=a;i>=b;i--)
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define INF (1000000000000000ll);
#define int ll
using namespace std;
using ll=long long;
using pii=pair<int,int>;
// color -> vector( (to,cost) )
map<int,vector<pii>> adj[100010];
map<int,int> cnt[100010];
vector<pii> g[100010];
int dist[100010];
int32_t main(){
ios::sync_with_stdio(false);
cin.tie(0);
// nachoneko sama & miku sama bless me >/////<
int n,m; cin>>n>>m;
For(i,1,m){
int a,b,c,p; cin>>a>>b>>c>>p;
adj[a][c].eb(b,p);
adj[b][c].eb(a,p);
cnt[a][c]++;
cnt[b][c]++;
}
For(i,1,n){
for(auto &item:adj[i]){
auto &ad=item.S;
if(sz(ad)==1){
g[i].eb(ad[0].F,0ll);
continue;
}
sort(all(ad),[](const pii &a,const pii &b){
return a.S>b.S;
});
int tot=0;
for(auto &j:ad) tot+=j.S;
for(auto &j:ad){
g[i].eb(j.F,j.S);
}
// leave the biggest edge, change the rest
g[i].eb(ad[0].F,tot-ad[0].S);
For(iter,1,sz(ad)-1){
g[ad[iter].F].eb(ad[0].F,tot-ad[0].S);
}
// leave the 2nd biggest edge, change the rest
g[i].eb(ad[1].F,tot-ad[1].S);
For(iter,0,sz(ad)-1) if(iter!=1){
g[ad[iter].F].eb(ad[1].F,tot-ad[1].S);
}
}
}
// dijkstra on g[]
memset(dist,-1,sizeof(dist));
priority_queue<pii,vector<pii>,greater<pii>> pq;
pq.emplace(0,1);
while(!pq.empty()){
int d=pq.top().F;
int now=pq.top().S;
pq.pop();
if(dist[now]!=-1) continue;
dist[now]=d;
for(auto &e:g[now]) if(dist[e.F]==-1){
pq.emplace(d+e.S,e.F);
}
}
cout<<dist[n]<<"\n";
return 0;
}
