#include <bits/stdc++.h>
#include <experimental/random>
#include <random>
using namespace std;
using ld = double;
using ll = long long;
const ll INF = 1e18, MOD = 1e9 + 7;
void solve();
signed main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int q = 1;
while (q--) {
solve();
}
}
struct ed {
int u, c, p, id1, id2;
};
void solve() {
int n, m; cin >> n >> m;
vector<vector<ed>> g(n);
vector<vector<int>> cord(n);
for (int i = 0; i < m; i++) {
int a, b, c, p; cin >> a >> b >> c >> p;
a--, b--;
g[a].push_back({b, c, p});
g[b].push_back({a, c, p});
cord[a].push_back(c);
cord[b].push_back(c);
}
vector<vector<ll>> sm(n);
vector<vector<ll>> dist(n);
vector<vector<vector<ed>>> colored(n);
for (int i = 0; i < n; i++) {
sort(cord[i].begin(), cord[i].end());
cord[i].resize(unique(cord[i].begin(), cord[i].end()) - cord[i].begin());
sm[i].resize(cord[i].size());
dist[i].resize(cord[i].size() + 1, INF);
colored[i].resize(cord[i].size());
for (auto &e : g[i]) {
int id = lower_bound(cord[i].begin(), cord[i].end(), e.c) - cord[i].begin();
sm[i][id] += e.p;
e.id1 = id;
colored[i][id].push_back(e);
}
}
for (int i = 0; i < n; i++) {
for (auto &e : g[i]) {
e.id2 = lower_bound(cord[e.u].begin(), cord[e.u].end(), e.c) - cord[e.u].begin();
}
}
dist[0][0] = 0;
set<pair<ll, pair<int, int>>> dj;
dj.insert({0, {0, 0}});
while (!empty(dj)) {
auto [v, c] = dj.begin()->second;
dj.erase(dj.begin());
if (c == 0) {
for (auto [u, color, p, id2, id] : g[v]) {
if (dist[u][id + 1] > dist[v][c]) {
dj.erase({dist[u][id + 1], {u, color}});
dist[u][id + 1] = dist[v][c];
dj.insert({dist[u][id + 1], {u, color}});
}
ll cost = min((ll)p, sm[v][id2] - p);
if (dist[u][0] > dist[v][c] + cost) {
dj.erase({dist[u][0], {u, 0}});
dist[u][0] = dist[v][c] + cost;
dj.insert({dist[u][0], {u, 0}});
}
}
} else {
ll z = lower_bound(cord[v].begin(), cord[v].end(), c) - cord[v].begin();
for (auto [u, color, p, idx, x] : colored[v][z]) {
ll cost = sm[v][idx] - p;
if (dist[u][0] > dist[v][idx + 1] + cost) {
dj.erase({dist[u][0], {u, 0}});
dist[u][0] = dist[v][idx + 1] + cost;
dj.insert({dist[u][0], {u, 0}});
}
}
}
}
if (dist[n - 1][0] >= INF) cout << -1;
else cout << dist[n - 1][0];
}
