#include <bits/stdc++.h>
#include <experimental/random>
#include <random>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
using ld = long 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;
//cin >> q;
while (q--) {
solve();
}
}
struct ed {
ll u, c, p;
bool operator<(ed x) const {
return c < x.c;
}
};
void solve() {
ll n, m; cin >> n >> m;
vector<vector<ed>> g(n + 2 * m);
for (int i = 0; i < m; i++) {
ll a, b, c, p; cin >> a >> b >> c >> p;
a--, b--;
g[a].push_back({i + n, c, p});
g[i + n].push_back({b, c, 0});
g[b].push_back({i + n + m, c, p});
g[i + n + m].push_back({a, c, 0});
}
for (int i = 0; i < n; i++) {
sort(g[i].begin(), g[i].end());
ll l = 0;
while (l < g[i].size()) {
ll r = l;
while (r < g[i].size() && g[i][r].c == g[i][l].c) {
r++;
}
if (r - l > 2) {
l = r;
continue;
}
if (r - l == 1) {
g[i][l].p = 0;
l = r;
continue;
}
ll u1 = g[i][l].u;
ll u2 = u1 + m;
if (u1 >= n + m) {
u2 = u1 - m;
}
ll v1 = g[i][l + 1].u;
ll v2 = v1 + m;
if (v1 >= n + m) {
v2 = v1 - m;
}
ll c = g[i][l].c;
g[u2].push_back({v1, c, 0});
g[v2].push_back({u1, c, 0});
l = r;
}
}
ll t = n - 1;
n = (int)g.size();
vector<ll> dist(n, INF);
dist[0] = 0;
set<pair<ll, ll>> dj;
dj.insert({0, 0});
while (!empty(dj)) {
ll v = dj.begin()->second;
dj.erase(dj.begin());
for (auto [u, c, p] : g[v]) {
if (dist[u] > dist[v] + p) {
dj.erase({dist[u], u});
dist[u] = dist[v] + p;
dj.insert({dist[u], u});
}
}
}
if (dist[t] >= INF) cout << -1;
else cout << dist[t];
}
