#include <bits/stdc++.h>
using namespace std;
struct segment_tree {
int lx, rx;
long long min_value, push;
int unused;
segment_tree* left = nullptr;
segment_tree* right = nullptr;
segment_tree(int _lx, int _rx) : lx(_lx), rx(_rx) {
min_value = push = LLONG_MAX;
unused = 0;
}
void apply(long long v) {
min_value = min(min_value, v);
push = min(push, v);
}
void propagate() {
if (push == LLONG_MAX) {
return;
}
if (left) {
left->apply(push);
}
if (right) {
right->apply(push);
}
push = LLONG_MAX;
}
void pull() {
min_value = push = LLONG_MAX;
unused = 0;
if (left) {
if (left->unused > 0) {
min_value = min(min_value, left->min_value);
unused += left->unused;
}
}
if (right) {
if (right->unused > 0) {
min_value = min(min_value, right->min_value);
unused += right->unused;
}
}
}
void Left() { left = (left ? left : new segment_tree(lx, (lx + rx) / 2)); }
void Right() { right = (right ? right : new segment_tree((lx + rx) / 2, rx)); }
void update(int l, int r, long long v) {
if (lx >= l && rx <= r) {
apply(v);
} else {
propagate();
int mid = (lx + rx) / 2;
if (l < mid) {
Left();
left->update(l, r, v);
}
if (r > mid) {
Right();
right->update(l, r, v);
}
pull();
}
}
void modify(int i, long long v, bool is_unused) {
if (rx - lx == 1) {
if (!is_unused) {
unused = 0;
min_value = push = LLONG_MAX;
} else {
unused = 1;
min_value = push = v;
}
} else {
propagate();
int mid = (lx + rx) / 2;
if (i < mid) {
Left();
left->modify(i, v, is_unused);
} else {
Right();
right->modify(i, v, is_unused);
}
pull();
}
}
pair<long long, int> get_min() {
if (unused == 0) {
return {LLONG_MAX, -1};
} else if (!left && !right) {
return {min_value, lx};
} else {
propagate();
bool left_good = left && left->min_value == min_value && left->unused > 0;
bool right_good = right && right->min_value == min_value && right->unused > 0;
if (left_good) {
return left->get_min();
} else if (right_good) {
return right->get_min();
} else {
if (left && (left->min_value != min_value || left->unused == 0)) {
return {min_value, (lx + rx) / 2};
} else {
return {min_value, lx};
}
}
}
}
};
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<pair<int, int>>>> g(n);
vector<segment_tree> st(n, segment_tree(0, 2 << __lg(m)));
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);
g[b][c].emplace_back(a, p);
sum[a][c] += p;
sum[b][c] += p;
}
min_heap<tuple<long long, int, int>> q;
for (int i = 1; i < n; i++) {
for (auto [color, value] : sum[i]) {
st[i].modify(color, LLONG_MAX, true);
}
}
for (auto [color, value] : sum[0]) {
q.emplace(0, 0, color);
dist[0][color] = 0;
}
set<pair<int, int>> used;
long long ans = LLONG_MAX;
while (!q.empty()) {
auto [d, u, nxt] = q.top();
q.pop();
if (used.count({u, nxt})) {
continue;
}
used.emplace(u, nxt);
st[u].modify(nxt, dist[u][nxt], false);
auto [MinValue, Pos] = st[u].get_min();
if (Pos != -1) {
dist[u][Pos] = MinValue;
q.emplace(MinValue, u, Pos);
}
auto S = sum[u][nxt], D = dist[u][nxt];
for (auto [v, p] : g[u][nxt]) {
if (v == n - 1) {
ans = min({ans, D + p, D + S - p});
}
st[v].update(0, 2 << __lg(m), D + p);
if (nxt > 0) {
st[v].update(0, nxt, D + S - p);
}
if (nxt + 1 < (2 << __lg(m))) {
st[v].update(nxt + 1, 2 << __lg(m), D + S - p);
}
auto [min_value, pos] = st[v].get_min();
if (pos != -1) {
if (dist[v].count(pos)) {
dist[v][pos] = min(dist[v][pos], min_value);
} else {
dist[v][pos] = min_value;
}
q.emplace(min_value, v, pos);
}
}
}
cout << (ans == LLONG_MAX ? -1 : ans) << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
