#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)4e18;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
vector<int> A(M), B(M), C(M);
vector<ll> P(M);
for (int i = 0; i < M; i++) {
cin >> A[i] >> B[i] >> C[i] >> P[i];
--A[i]; --B[i];
}
// Danh sách các cạnh theo đỉnh
vector<vector<int>> inc(N);
for (int i = 0; i < M; i++) {
inc[A[i]].push_back(i);
inc[B[i]].push_back(i);
}
// Xây danh sách cạnh có hướng với trọng số
vector<vector<pair<int,ll>>> adj(N);
// Xét từng đỉnh, nhóm các cạnh theo màu
vector<int> tmp = { }; tmp.reserve(1000);
for (int u = 0; u < N; u++) {
auto &v = inc[u];
// sort thứ tự theo màu
sort(v.begin(), v.end(), [&](int i, int j) {
return C[i] < C[j];
});
int L = v.size();
int idx = 0;
while (idx < L) {
int j = idx;
ll sumP = 0;
// nhóm cùng màu C[v[idx]]
while (j < L && C[v[j]] == C[v[idx]]) {
sumP += P[v[j]];
j++;
}
// với mỗi cạnh trong nhóm, tính trọng số hướng từ u
for (int k = idx; k < j; k++) {
int ei = v[k];
// chi phí đổi tất cả cạnh còn lại trong nhóm:
ll cost_conflict = sumP - P[ei];
ll w = min(P[ei], cost_conflict);
// xác định đỉnh kề
int to = (A[ei] == u ? B[ei] : A[ei]);
adj[u].emplace_back(to, w);
}
idx = j;
}
}
// Dijkstra từ 0 đến N-1
vector<ll> dist(N, INF);
dist[0] = 0;
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
pq.emplace(0, 0);
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;
if (u == N-1) break;
for (auto &e: adj[u]) {
int v = e.first;
ll w = e.second;
if (dist[v] > d + w) {
dist[v] = d + w;
pq.emplace(dist[v], v);
}
}
}
if (dist[N-1] == INF) cout << -1;
else cout << dist[N-1];
cout << '\n';
return 0;
}
