//#pragma GCC optimize ("O3")
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
#include <cassert>
#include<algorithm>
#include <cstring>
#include<unordered_set>
#include<queue>
#include <array>
#include<cmath>
#include<unordered_map>
#include<queue>
#include <list>
#include <bitset>
using namespace std;
#define int long long
#define pii pair<int,int>
#define LL long long
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt”)
struct road{
int dest, color, cost;
};
int INF = 1e18;
int n, m;
vector<map<int, int>>col_freqs;
vector<vector<road>>adj;
map<pii, int>gethash;
vector<pii>getpair(50001);
void disjkstra(){
vector<int>dist(50001, INF);
dist[gethash[{0, 0}]] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
pq.push({0, gethash[{0, 0}]});
while(!pq.empty()){
int d = pq.top().first;
int h = pq.top().second;
auto [node, col_used] = getpair[pq.top().second];
pq.pop();
if(dist[h] > d){
continue;
}
//visit neighbors
for(auto [b, col, price] : adj[node]){
int colfreq = col_freqs[node][col];
if(col == col_used){
//cout << d << " " << node << endl;
colfreq--;
}
if(colfreq <= 1){
//cost is nothing
int newhash = gethash[{b, 0}];
if(d < dist[newhash]){
//push it
dist[newhash] = d;
pq.push({d, newhash});
}
} else{
//cost is the price
int newhash = gethash[{b, col}];
if(d + price < dist[newhash]){
dist[newhash] = d + price;
pq.push({d + price, newhash});
}
}
}
}
//find the in of the dist[gethash[{n-1,x}]], where x can be anything
int ans = INF;
for(int i = 0; i <= m; ++i){
ans = min(ans, dist[gethash[{n - 1, i}]]);
}
if(ans == INF){
cout << "-1";
} else{
cout << ans;
}
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
adj = vector<vector<road>>(n);
col_freqs = vector<map<int, int>>(n);
int ind = 0;
for(int i = 0; i < m; ++i){
int a, b, col, cost;
cin >> a >> b >> col >> cost;
--a; --b;
adj[a].push_back({b, col, cost});
adj[b].push_back({a, col, cost});
col_freqs[a][col]++;
col_freqs[b][col]++;
if(!gethash.count((pii){ a, col })){
gethash[(pii){ a, col }] = ind;
getpair[ind] = (pii){a, col};
ind++;
}
if(!gethash.count((pii){ b, col })){
gethash[(pii){ b, col }] = ind;
getpair[ind] = (pii){b, col};
ind++;
}
}
for(int i = 0; i < n; ++i){
gethash[{i, 0}] = ind;
getpair[ind] = {i, 0};
ind++;
}
disjkstra();
}
