#include <bits/stdc++.h>
using namespace std;
struct container {
int a = -1;
long long x = LLONG_MAX, y = LLONG_MAX;
vector<int> S;
container() {}
container(vector<int> s) : S(s) {}
void update_all(long long v) {
x = min(x, v);
y = min(y, v);
}
void update_exclusive(int i, long long v) {
if (v < x) {
if (a != i) {
y = x;
a = i;
}
x = v;
} else {
if (a != i) {
y = min(y, v);
}
}
}
pair<long long, int> get_min() {
if (S.empty()) {
return {LLONG_MAX, -1};
} else if (S.size() == 1) {
return {(S.back() == a ? y : x), S.back()};
} else {
return {x, (S.back() == a ? end(S)[-2] : S.back())};
}
}
void pop() {
assert(!S.empty());
if (S.back() == a) {
if (S.size() == 1) {
S.pop_back();
x = y = LLONG_MAX;
} else {
S.pop_back();
S.pop_back();
S.push_back(a);
}
} else {
S.pop_back();
}
}
};
template <typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
void solve() {
int n, m;
cin >> n >> m;
vector<map<int, long long>> sum(n), dist(n);
vector<map<int, vector<tuple<int, int, int>>>> g(n);
vector<container> C(n);
for (int i = 0; i < m; i++) {
int a, b, c, p;
cin >> a >> b >> c >> p;
a--, b--;
g[a][c].emplace_back(b, p, c);
g[b][c].emplace_back(a, p, c);
sum[a][c] += p;
sum[b][c] += p;
}
min_heap<tuple<long long, int, int, bool>> q;
for (int i = 0; i < n; i++) {
vector<int> d;
for (auto [k, v] : sum[i]) {
d.push_back(k);
dist[i][k] = LLONG_MAX;
}
d.push_back(m + 1 + i);
dist[i][m + 1 + i] = LLONG_MAX;
vector<tuple<int, int, int>> gc;
for (auto [k, cc] : g[i]) {
for (auto [v, p, col] : cc) {
gc.emplace_back(v, p, col);
}
}
g[i][m + 1 + i] = gc;
sort(d.begin(), d.end());
d.resize(unique(d.begin(), d.end()) - d.begin());
C[i] = container(d);
if (i == 0) {
for (int v : d) {
q.emplace(0, 0, v, true);
dist[0][v] = 0;
}
}
}
long long ans = LLONG_MAX;
while (!q.empty()) {
auto [d, u, nxt, del] = q.top();
q.pop();
if (d > dist[u][nxt]) {
continue;
}
if (del) {
C[u].pop();
if (!C[u].S.empty()) {
auto [min_value, pos] = C[u].get_min();
if (!dist[u].count(pos) || dist[u][pos] > min_value) {
dist[u][pos] = min_value;
q.emplace(min_value, u, pos, true);
}
}
}
long long D = dist[u][nxt], S = sum[u][nxt];
for (auto [v, p, col] : g[u][nxt]) {
if (v == n - 1) {
ans = min({ans, (nxt == m + 1 + u ? D + p : LLONG_MAX), (nxt == m + 1 + u ? LLONG_MAX : D + S - p)});
}
if (nxt != m + 1 + u) {
C[v].update_exclusive(nxt, D + S - p);
} else {
C[v].update_all(D + p);
if (!dist[v].count(col) || dist[v][col] > D) {
dist[v][col] = D;
q.emplace(dist[v][col], v, col, false);
}
}
if (!C[v].S.empty()) {
auto [min_value, pos] = C[v].get_min();
if (!dist[v].count(pos) || dist[v][pos] > min_value) {
dist[v][pos] = min_value;
q.emplace(min_value, v, pos, true);
}
}
}
}
cout << (ans == LLONG_MAX ? -1 : ans) << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
