#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;
if (!(cin >> N >> M)) return 0;
// V[u] : các cạnh kề với u, lưu (màu, (chi phí P, đỉnh kề))
vector<vector<pair<int, pair<ll,int>>>> V(N + 1);
for (int i = 0; i < M; ++i) {
int a, b, c;
ll p;
cin >> a >> b >> c >> p;
V[a].push_back({c, {p, b}});
V[b].push_back({c, {p, a}});
}
// Số đỉnh tối đa trong đồ thị mở rộng:
// ban đầu có N đỉnh gốc, thêm tối đa 2*M đỉnh màu-đỉnh
int maxNodes = N + 2 * M + 5;
vector<vector<pair<ll,int>>> G(maxNodes); // G[u] : (cost, v)
int sz = N; // đếm số đỉnh hiện tại trong đồ thị mở rộng
// Xây đồ thị mở rộng
for (int u = 1; u <= N; ++u) {
if (V[u].empty()) continue;
// Gom các cạnh theo màu
auto &vec = V[u];
sort(vec.begin(), vec.end(),
[](const auto &A, const auto &B) {
if (A.first != B.first) return A.first < B.first;
// phụ cho ổn định, không bắt buộc
return A.second.second < B.second.second;
});
int nAdj = (int)vec.size();
int l = 0;
while (l < nAdj) {
int r = l;
int color = vec[l].first;
ll sumP = 0;
// [l, r) là nhóm cùng màu "color" tại đỉnh u
while (r < nAdj && vec[r].first == color) {
sumP += vec[r].second.first;
++r;
}
int cnt = r - l;
if (cnt == 1) {
// Chỉ có 1 cạnh màu này ở u:
// đi qua cạnh này từ u sang v với cost 0
int v = vec[l].second.second;
G[u].push_back({0, v});
} else {
// Có >= 2 cạnh cùng màu tại u
// tạo đỉnh trung gian nodeColor = (u, color)
int nodeColor = ++sz;
// từ u sang nodeColor (chuẩn bị thực hiện move Y) với cost 0
G[u].push_back({0, nodeColor});
// duyệt từng cạnh trong nhóm
for (int j = l; j < r; ++j) {
ll p = vec[j].second.first;
int v = vec[j].second.second;
// 1) di chuyển kiểu X: tô riêng cạnh này, từ u sang v, cost = p
G[u].push_back({p, v});
// 2) bước X của cặp (X,Y): từ v sang nodeColor với cost 0
G[v].push_back({0, nodeColor});
// 3) bước Y: từ nodeColor sang v, cost = tổng P các cạnh cùng màu trừ cạnh này
G[nodeColor].push_back({sumP - p, v});
}
}
l = r;
}
}
// Dijkstra trên đồ thị mở rộng
vector<ll> dist(sz + 1, INF);
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
dist[1] = 0;
pq.push({0, 1});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d != dist[u]) continue;
for (auto [w, v] : G[u]) {
if (dist[v] > d + w) {
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}
if (dist[N] == INF) cout << -1;
else cout << dist[N];
return 0;
}
