//#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”)
int INF = 1e18;
int n, m;
vector<map<int, int>>col_prices;
vector<vector<int>>adj;
map<pii, int>gethash;
vector<pii>getpair(70001);
vector<pair<pii, pii>>edges;
void disjkstra(){
vector<int>dist(70001, 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, edge_used] = getpair[pq.top().second];
pq.pop();
if(dist[h] > d){
continue;
}
//visit neighbors
for(auto e : adj[node]){
auto [nodes, info] = edges[e];
auto [a, b] = nodes;
int dest = a == node ? b : a;
auto [col, p] = info;
int totcost = col_prices[node][col];
int everything_cost = col_prices[node][col] - p;
int paintyou_cost = p;
if(col == edges[edge_used].second.first){
//this means that the cost of painting everything is -edge[edges_used].second.second
//paint cost is either painting everything except for it or just painting it
everything_cost -= edges[edge_used].second.second;
}
int hash1 = gethash[{dest, e}];
int hash2 = gethash[{dest, 0}];
if(d + p < dist[hash1]){
dist[hash1] = d + p;
pq.push({d + p, hash1});
}
if(d + everything_cost < dist[hash2]){
dist[hash2] = d + everything_cost;
pq.push({d + everything_cost, hash2});
}
}
}
//find the in of the dist[gethash[{n-1,x}]], where x can be anything
int ans = INF;
for(int e : adj[n - 1]){
ans = min(ans, dist[gethash[{n - 1, e}]]);
}
ans = min(ans, dist[gethash[{n - 1, 0}]]);
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<int>>(n);
col_prices = vector<map<int, int>>(n);
edges = vector<pair<pii, pii>>(m + 1);
int ind = 0;
for(int i = 1; i <= m; ++i){
int a, b, col, cost;
cin >> a >> b >> col >> cost;
--a; --b;
adj[a].push_back(i);
adj[b].push_back(i);
edges[i] = {{a, b}, {col, cost}};
col_prices[a][col] += cost;
col_prices[b][col] += cost;
if(!gethash.count((pii){ a, i })){
gethash[(pii){ a, i }] = ind;
getpair[ind] = (pii){a, i};
ind++;
}
if(!gethash.count((pii){ b, i })){
gethash[(pii){ b, i }] = ind;
getpair[ind] = (pii){b, i};
ind++;
}
}
for(int i = 0; i < n; ++i){
gethash[{i, 0}] = ind;
getpair[ind] = {i, 0};
ind++;
}
return 0;
disjkstra();
}
