#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define dbg(x) cerr << #x << ": " << x << endl;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> g(n);
vector<int> color(m + 1);
vector<int> cost(m + 1);
vector<map<int, ll>> color_cost(n);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
cin >> color[i] >> cost[i];
g[u].emplace_back(v, i);
g[v].emplace_back(u, i);
color_cost[u][color[i]] += cost[i];
color_cost[v][color[i]] += cost[i];
}
const ll INF = 1e18;
vector<ll> dist(n, INF);
vector<bool> used(n);
const int SPECIAL = n;
g[0].emplace_back(SPECIAL, m);
for (int v = 0; v < n; ++v) {
sort(g[v].begin(), g[v].end());
}
priority_queue<tuple<ll, int, int, int>, vector<tuple<ll, int, int, int>>, greater<tuple<ll, int, int, int>>> pq;
pq.emplace(0, 0, 0, g[0].size() - 1);
while (!pq.empty()) {
auto [curr_dist, v, t, idx] = pq.top();
pq.pop();
if (used[v]) continue;
used[v] = true;
dist[v] = curr_dist;
int prev_edge = g[v][idx].second;
for (const auto& [u, new_edge] : g[v]) {
if (u == SPECIAL) continue;
if (new_edge == prev_edge) continue;
int new_idx = lower_bound(g[u].begin(), g[u].end(), make_pair(v, -1)) - g[u].begin();
if (!used[u] && dist[u] > curr_dist + cost[new_edge]) {
dist[u] = curr_dist + cost[new_edge];
pq.emplace(dist[u], u, 0, new_idx);
}
if (t == 1 && color[new_edge] == color[prev_edge]) continue;
ll new_cost = color_cost[v][color[new_edge]] - cost[new_edge];
if (t == 0 && color[new_edge] == color[prev_edge]) new_cost -= cost[prev_edge];
if (!used[u] && dist[u] > curr_dist + new_cost) {
dist[u] = curr_dist + new_cost;
pq.emplace(dist[u], u, 1, new_idx);
}
}
}
if (!used[n - 1]) {
cout << "-1\n";
} else {
cout << dist[n - 1] << '\n';
}
return 0;
}
