#include "bits/stdc++.h"
#define int long long
using namespace std;
const long long INF = LLONG_MAX;
int32_t main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, m; cin >> n >> m;
vector<vector<pair<int, int>>> f(n + 1), g(n + 1);
for (int i = 0; i < m; i++) {
int a, b, c, d; cin >> a >> b >> c >> d;
f[a].push_back({b, c});
f[b].push_back({a, c});
g[a].push_back({b, d});
g[b].push_back({a, d});
}
for (int x = 1; x <= n; x++) {
multiset<int> st;
for (auto [k, c] : f[x])
st.insert(c);
for (auto [k, c] : f[x])
if (st.count(c) == 1)
g[x].push_back({k, 0});
}
using T = pair<int, int>;
priority_queue<T, vector<T>, greater<T>> pq;
vector<int> dist(n + 1, INF);
auto push = [&](int x, int d) -> void {
if (d < dist[x])
pq.push({dist[x] = d, x});
};
push(1, 0);
while (!pq.empty()) {
auto [d, x] = pq.top(); pq.pop();
if (dist[x] != d) continue;
for (auto [k, dd] : g[x])
push(k, d + dd);
}
cout << (dist[n] == INF ? -1 : dist[n]) << '\n';
return 0;
}
