/*
Implementation of Aruj's idea of splitting cases into "forcibly recolour others" and "anything is ok"
*/
#include <bits/stdc++.h>
using namespace std;
void fast() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
}
void ran() {
srand(chrono::steady_clock::now().time_since_epoch().count());
}
long long get_rand() {
long long a = rand();
long long b = rand();
return a * (RAND_MAX + 1ll) + b;
}
void usaco() {
freopen("problem.in", "r", stdin);
freopen("problem.out", "w", stdout);
}
template<typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
#define endl '\n'
// #define double long double
// #define int long long
// const int MOD = 1000 * 1000 * 1000 + 7;
// const int MOD = 998244353;
// #define cerr if(0) cerr
#define debug(x) cerr << #x << ": " << x << endl;
int n, m;
const int MXN = 100005;
const int MXM = 200005;
int a[MXM], b[MXM], colour[MXM], price[MXM];
vector<pair<int, int>> adj[MXN];
map<int, long long> adj_sum[MXN];
map<int, vector<pair<int, int>>> adjbycolour[MXN];
map<pair<int, int>, long long> dist;
long long getdist(int no, int co) {
pair<int, int> tr = {no, co};
auto f = dist.find(tr);
if (f == dist.end()) return LLONG_MAX / 4;
return f->second;
}
void setdist(int no, int co, int to) {
dist[{no, co}] = to;
}
signed main() {
ran(); fast();
cin >> n >> m;
for (int i=1; i<=m; i++) {
cin >> a[i] >> b[i] >> colour[i] >> price[i];
adj[a[i]].push_back({i, 1}); // connect it to the other side
adj[b[i]].push_back({i, 0}); // connect it to the other side
adj_sum[a[i]][colour[i]]+=price[i];
adj_sum[b[i]][colour[i]]+=price[i];
adjbycolour[a[i]][colour[i]].push_back({i, 1});
adjbycolour[b[i]][colour[i]].push_back({i, 0});
}
min_pq<pair<long long, pair<int, int>>> proc;
proc.push({0, {1, -1}});
while (!proc.empty()) {
auto f = proc.top(); proc.pop();
int di = f.first, no = f.second.first, co = f.second.second;
if (getdist(no, co) < di) continue;
setdist(no, co, di);
// cout << no << " " << co << ": " << di << endl;
if (co == -1) {
// go anywhere tbh
for (auto x: adj[no]) {
int edge_num = x.first, ot = x.second;
int other = a[edge_num];
if (ot == 1) other = b[edge_num];
// either recolour this one edge, paying price[edge_num]
long long od = getdist(other, -1); // you'll end somewhere without restriction
if (di + price[edge_num] < od) {
setdist(other, -1, di + price[edge_num]);
proc.push({di + price[edge_num], {other, -1}});
}
// or recolour this edge, but pay later by forcing the same colour to be used next time
od = getdist(other, colour[edge_num]);
if (di < od) {
setdist(other, colour[edge_num], di);
proc.push({di, {other, colour[edge_num]}});
}
// or recolour all the other edges of this colour, paying the price here
od = getdist(other, -1);
long long cost = adj_sum[no][colour[edge_num]] - price[edge_num];
if (cost + di < od) {
setdist(other, -1, cost + di);
proc.push({cost+di, {other, -1}});
}
}
}
else {
// you have agreed to take only certain coloured edges, and also to not recolour only the edge you take out of here
// ie you must recolour all other edges of whatever colour you take
int sm = adj_sum[no][co];
for (auto x: adjbycolour[no][co]) {
int edge_num = x.first, ot = x.second;
int other = a[edge_num];
if (ot == 1) other = b[edge_num];
long long od = sm - price[edge_num] + di;
long long curr = getdist(other, -1);
if (od < curr) {
setdist(od, other, -1);
proc.push({od, {other, -1}});
}
}
}
}
long long res = getdist(n, -1);
if (res == LLONG_MAX / 4) cout << -1 << endl;
else cout << res << endl;
}
