#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<int,pii>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
void solve(){
int n,m;
cin >> n >> m;
int temp,temp2,temp3,temp4;
vector<pair<int,pii>>adj[n+5];
unordered_map<int,vector<pii>>adj2[n+5];
map<pii,int>mp;
for(int x=0;x<m;x++){
cin >> temp >> temp2 >> temp3 >> temp4;
adj[temp].push_back({temp2,{temp3,temp4}});
adj[temp2].push_back({temp,{temp3,temp4}});
mp[{temp,temp3}]+=temp4;
mp[{temp2,temp3}]+=temp4;
adj2[temp][temp3].push_back({temp2,temp4});
adj2[temp2][temp3].push_back({temp,temp4});
}
unordered_map<int,int>dist[n+5];
priority_queue<pi2,vector<pi2>,greater<pi2>>pq;
dist[1][0]=0;
pq.push({0,{1,0}});
for(auto it:adj2[1]){
dist[1][it.first]=mp[{1,it.first}];
pq.push({mp[{1,it.first}],{1,it.first}});
}
while(!pq.empty()){
pi2 cur=pq.top();
pq.pop();
int index=cur.second.first;
int col=cur.second.second;
int d=cur.first;
//show3(index,index,col,col,d,d);
if(dist[index][col]!=d) continue;
if(col!=0){
for(auto it:adj2[index][col]){
int nx=it.first;
int cost=it.second;
int nd=d-cost;
if(dist[nx].find(0)==dist[nx].end()||dist[nx][0]>nd){
dist[nx][0]=nd;
pq.push({nd,{nx,0}});
}
}
}
for(auto it:adj[index]){
int nx=it.first;
int a=it.second.first;
int cost=it.second.second;
//no charge
int nd=d+cost;
if(mp[{index,a}]==cost) nd=d;
if(dist[nx].find(0)==dist[nx].end()||dist[nx][0]>nd){
dist[nx][0]=nd;
pq.push({nd,{nx,0}});
}
//charge
nd=d+mp[{nx,a}];
if(dist[nx].find(a)==dist[nx].end()||dist[nx][a]>nd){
dist[nx][a]=nd;
pq.push({nd,{nx,a}});
}
}
}
int best=1e18;
for(int x=0;x<=m;x++){
if(dist[n].find(x)!=dist[n].end()){
best=min(best,dist[n][x]);
}
}
if(best==1e18) cout << -1;
else cout << best;
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int t=1;
//cin >> t;
while(t--){
solve();
}
}
