#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 4e5;
vector<array<int, 3>> edges[MAXN + 1];
vector<array<ll, 2>> adj[MAXN + 1];
void add_edge(int s, int e, ll w) {
adj[s].push_back({e, w});
}
vector<array<int, 2>> out[MAXN + 1];
vector<int> in[MAXN + 1];
ll costOut[MAXN + 1];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
int idx = n;
for (int i = 0; i < m; ++i) {
int a, b, c, w;
cin >> a >> b >> c >> w;
edges[c].push_back({a, b, w});
edges[c].push_back({b, a, w});
}
for (int i = 1; i <= m; ++i) {
for (auto& [s, e, w] : edges[i]) {
in[e].push_back(s);
out[s].push_back({e, w});
costOut[s] += w;
}
for (auto& [s, e, w] : edges[i]) {
add_edge(s, e, min(1LL * w, 1LL * costOut[s] - w));
if ((int)out[s].size() > 0) {
idx += 1;
for (auto& [e, w] : out[s]) {
add_edge(idx, e, costOut[s] - w);
}
for (auto& e : in[s]) {
add_edge(e, idx, 0);
}
out[s].clear();
}
}
for (auto& [s, e, w] : edges[i]) {
in[e].clear();
costOut[s] = 0;
}
}
priority_queue<array<ll, 2>> pq;
vector<ll> dist(idx + 1, (ll)1e18);
pq.push({0, 1});
dist[1] = 0;
while (pq.size()) {
ll cost = -pq.top()[0];
int v = pq.top()[1];
pq.pop();
if (dist[v] != cost) continue;
//~ cerr << v << " = " << cost << "\n";
for (auto& [u, w] : adj[v]) {
if (cost + w < dist[u]) {
dist[u] = cost + w;
pq.push({-dist[u], u});
}
}
}
if (dist[n] > (ll)1e17) dist[n] = -1;
cout << dist[n] << "\n";
}
