#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
const long long INF = 1e18;
struct Edge {
int to, color, cost, idx;
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
cin >> N >> M;
vector<int> A(M), B(M), C(M), P(M);
vector<vector<Edge>> graph(N);
for (int i = 0; i < M; i++) {
cin >> A[i] >> B[i] >> C[i] >> P[i];
A[i]--; B[i]--;
graph[A[i]].push_back({B[i], C[i], P[i], i});
graph[B[i]].push_back({A[i], C[i], P[i], i});
}
// For each vertex, for each color, store sum of costs and min cost
vector<map<int, long long>> colorSum(N);
vector<map<int, int>> colorMin(N);
vector<map<int, int>> colorCount(N);
for (int i = 0; i < N; i++) {
map<int, vector<int>> costsByColor;
for (const auto& e : graph[i]) {
costsByColor[e.color].push_back(e.cost);
}
for (const auto& [color, costs] : costsByColor) {
colorCount[i][color] = costs.size();
long long sum = 0;
int minCost = INF;
for (int c : costs) {
sum += c;
minCost = min(minCost, c);
}
colorSum[i][color] = sum;
colorMin[i][color] = minCost;
}
}
// Build adjacency list for Dijkstra
// Nodes: 0..N-1 (original vertices)
// For each edge i, we create two nodes:
// N + 2*i (u->v) and N + 2*i + 1 (v->u)
vector<vector<pair<int, long long>>> adj(N + 2*M);
for (int i = 0; i < M; i++) {
int u = A[i], v = B[i];
int col = C[i], cost = P[i];
int edgeUtoV = N + 2*i;
int edgeVtoU = N + 2*i + 1;
// Connect edge nodes to destination vertices
adj[edgeUtoV].push_back({v, 0});
adj[edgeVtoU].push_back({u, 0});
// Connect from source vertices to edge nodes with appropriate costs
// For u -> v
if (colorCount[u][col] == 1) {
adj[u].push_back({edgeUtoV, 0});
} else {
// Option 1: Change this edge's color
long long option1 = cost;
// Option 2: Change all other edges of this color at u
long long option2 = colorSum[u][col] - colorMin[u][col];
adj[u].push_back({edgeUtoV, min(option1, option2)});
}
// For v -> u
if (colorCount[v][col] == 1) {
adj[v].push_back({edgeVtoU, 0});
} else {
// Option 1: Change this edge's color
long long option1 = cost;
// Option 2: Change all other edges of this color at v
long long option2 = colorSum[v][col] - colorMin[v][col];
adj[v].push_back({edgeVtoU, min(option1, option2)});
}
// Also connect edges to each other through vertices
// This is handled by going edge -> vertex -> next edge
}
// Dijkstra from node 0
vector<long long> dist(N + 2*M, INF);
dist[0] = 0;
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
pq.push({0, 0});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
for (const auto& [v, w] : adj[u]) {
if (dist[v] > d + w) {
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}
long long ans = dist[N-1];
if (ans >= INF) {
cout << "-1\n";
} else {
cout << ans << "\n";
}
return 0;
}
