#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> g(n); //to, weight
vector<int> c(m), p(m), a(m), b(m);
vector<map<int, int>> cnt(n);
for (int i = 0; i < m; ++i) {
cin >> a[i] >> b[i] >> c[i] >> p[i];
--a[i], --b[i];
++cnt[a[i]][c[i]];
++cnt[b[i]][c[i]];
}
for (int i = 0; i < m; ++i) {
if (cnt[a[i]][c[i]] == 1) {
g[a[i]].emplace_back(b[i], 0);
} else {
g[a[i]].emplace_back(b[i], p[i]);
}
if (cnt[b[i]][c[i]] == 1) {
g[b[i]].emplace_back(a[i], 0);
} else {
g[b[i]].emplace_back(a[i], p[i]);
}
}
const ll inf = 1e18;
vector<ll> dist(n, inf);
dist[0] = 0;
set<pair<ll, int>> st;
st.insert({0, 0});
while (!st.empty()) {
auto [ww, v] = *st.begin();
st.erase(st.begin());
for (auto [to, w] : g[v]) {
if (dist[to] > dist[v] + w) {
st.erase({dist[to], to});
dist[to] = dist[v] + w;
st.insert({dist[to], to});
}
}
}
cout << (dist[n - 1] == inf ? -1 : dist[n - 1]);
return 0;
}
