#include <iostream>
#include <vector>
#include <array>
#include <utility>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<array<int, 3>>> adj(n);
for (int i = 0; i < m; i++) {
int a, b, c, p;
cin >> a >> b >> c >> p;
a--; b--;
adj[a].push_back({ c, p, b });
adj[b].push_back({ c, p, a });
}
vector<vector<long long>> dp(n);
vector<vector<pair<int, long long>>> total(n);
for (int i = 0; i < n; i++) {
sort(adj[i].begin(), adj[i].end());
for (int j = 0; j < adj[i].size(); j++) {
if (j == 0 || total[i][total[i].size() - 1].first != adj[i][j][0])
total[i].push_back({ adj[i][j][0], 0 });
total[i][total[i].size() - 1].second += adj[i][j][1];
}
dp[i].resize(adj[i].size() + 1, 1e18);
}
priority_queue<pair<long long, array<int, 5>>> q;
q.push({ 0, { 0, 0, 0, 0, 0 } });
while (!q.empty()) {
auto [ nd, x ] = q.top();
// from v to u
auto [ t, c, p, u, v ] = x;
long long d = -nd;
q.pop();
if (dp[u][dp[u].size() - 1] > d) {
dp[u][dp[u].size() - 1] = d;
for (auto arr : adj[u]) {
long long tot = (*lower_bound(total[u].begin(), total[u].end(), make_pair(arr[0], -1LL))).second;
q.push({ -(d + tot - arr[1]), { 0, 0, 0, arr[2], u } });
q.push({ -(d + arr[1]), { 1, arr[0], arr[1], arr[2], u } });
}
}
if (t == 1) {
auto st = lower_bound(adj[u].begin(), adj[u].end(), array<int, 3>{ c, p, v });
int i = st - adj[u].begin();
if (dp[u][i] <= d) continue;
dp[u][i] = d;
auto it = lower_bound(adj[u].begin(), adj[u].end(), array<int, 3>{ c + 1, -1, 0 });
it--;
if (it == st) {
if (it == adj[u].begin()) continue;
else it--;
}
if ((*it)[0] != c) continue;
long long tot = (*lower_bound(total[u].begin(), total[u].end(), make_pair(c, -1LL))).second;
auto [ c2, p2, v2 ] = *it;
q.push({ -(d + tot - p - p2), { 0, 0, 0, v2, u } });
}
}
long long ans = 1e18;
for (auto e : dp[n - 1])
ans = min(ans, e);
if (ans == 1e18) cout << -1;
else cout << ans;
return 0;
}
