#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
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, group edges by color and calculate total cost
vector<map<int, long long>> colorSum(N);
vector<map<int, int>> colorCount(N);
for (int i = 0; i < N; i++) {
for (const auto& e : graph[i]) {
colorCount[i][e.color]++;
colorSum[i][e.color] += e.cost;
}
}
// Create graph: vertices are (original vertex, edge index for outgoing edge)
// But simpler: use 2*M + N vertices
// 0..N-1: original vertices
// N + 2*i: outgoing edge i from A[i] to B[i]
// N + 2*i + 1: outgoing edge i from B[i] to A[i]
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];
// Directed edge u->v
int edgeId1 = N + 2*i;
// Directed edge v->u
int edgeId2 = N + 2*i + 1;
// Connect edge to destination vertex
adj[edgeId1].push_back({v, 0});
adj[edgeId2].push_back({u, 0});
// Connect from source vertex to edge
// Cost to use u->v from u
if (colorCount[u][col] == 1) {
adj[u].push_back({edgeId1, 0});
} else {
// Find minimum cost among edges of color col at vertex u
long long minCost = INF;
for (const auto& e : graph[u]) {
if (e.color == col) {
minCost = min(minCost, (long long)e.cost);
}
}
long long sum = colorSum[u][col];
long long otherSum = sum - minCost;
adj[u].push_back({edgeId1, min((long long)cost, otherSum)});
}
// Cost to use v->u from v
if (colorCount[v][col] == 1) {
adj[v].push_back({edgeId2, 0});
} else {
// Find minimum cost among edges of color col at vertex v
long long minCost = INF;
for (const auto& e : graph[v]) {
if (e.color == col) {
minCost = min(minCost, (long long)e.cost);
}
}
long long sum = colorSum[v][col];
long long otherSum = sum - minCost;
adj[v].push_back({edgeId2, min((long long)cost, otherSum)});
}
}
// Dijkstra from node 0 (crossing 1)
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;
}
