#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
struct Edge {
int to, color, cost;
};
struct Node {
long long d;
int u, c;
bool operator>(const Node& other) const { return d > other.d; }
};
const long long INF = 1e16; // Đủ lớn cho 2e5 * 1e6
vector<Edge> adj[100005];
map<int, long long> sum_c[100005];
map<int, long long> dist[100005];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v, c, p;
cin >> u >> v >> c >> p;
adj[u].push_back({v, c, p});
adj[v].push_back({u, c, p});
sum_c[u][c] += p;
sum_c[v][c] += p;
}
priority_queue<Node, vector<Node>, greater<Node>> pq;
// dist[u][0] là khoảng cách ngắn nhất đến u mà không bị ràng buộc màu
// dist[u][c] là khoảng cách ngắn nhất đến u thông qua cạnh màu c (chưa đổi màu c)
dist[1][0] = 0;
pq.push({0, 1, 0});
while (!pq.empty()) {
Node top = pq.top();
pq.pop();
int u = top.u;
int c = top.c;
long long d = top.d;
if (d > dist[u][c]) continue;
if (c == 0) {
for (auto& e : adj[u]) {
// TH1: Đổi màu duy nhất cạnh (u, v) -> tốn p
if (dist[e.to].find(0) == dist[e.to].end() || dist[e.to][0] > d + e.cost) {
dist[e.to][0] = d + e.cost;
pq.push({dist[e.to][0], e.to, 0});
}
// TH2: Đổi màu tất cả các cạnh cùng màu c tại u (trừ cạnh này) -> tốn Sum - p
long long cost_all = sum_c[u][e.color] - e.cost;
if (dist[e.to].find(0) == dist[e.to].end() || dist[e.to][0] > d + cost_all) {
dist[e.to][0] = d + cost_all;
pq.push({dist[e.to][0], e.to, 0});
}
// TH3: Đi vào trạng thái "đang xử lý màu c", không tốn phí ở bước này
if (dist[e.to].find(e.color) == dist[e.to].end() || dist[e.to][e.color] > d) {
dist[e.to][e.color] = d;
pq.push({dist[e.to][e.color], e.to, e.color});
}
}
} else {
// Đang ở trạng thái đặc biệt: đến u bằng màu c (của Strategy B)
for (auto& e : adj[u]) {
if (e.color == c) {
// Chỉ đi tiếp các cạnh cùng màu c để hưởng ưu đãi phí
long long cost_rem = sum_c[u][c] - e.cost;
if (dist[e.to].find(0) == dist[e.to].end() || dist[e.to][0] > d + cost_rem) {
dist[e.to][0] = d + cost_rem;
pq.push({dist[e.to][0], e.to, 0});
}
}
}
}
}
if (dist[n].find(0) == dist[n].end()) cout << -1 << endl;
else cout << dist[n][0] << endl;
return 0;
}
