#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
struct Edge {
int to, color;
ll cost;
int id;
};
struct State {
ll d;
int u, color, edge_idx;
bool operator>(const State& other) const { return d > other.d; }
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
vector<vector<Edge>> adj(N + 1);
vector<map<int, ll>> color_sum(N + 1);
for (int i = 0; i < M; ++i) {
int u, v, c;
ll p;
cin >> u >> v >> c >> p;
adj[u].push_back({v, c, p, i});
adj[v].push_back({u, c, p, i});
color_sum[u][c] += p;
color_sum[v][c] += p;
}
priority_queue<State, vector<State>, greater<State>> pq;
vector<ll> dist(N + 1, INF);
vector<ll> dist_edge(M, INF);
dist[1] = 0;
pq.push({0, 1, 0, -1});
while (!pq.empty()) {
State top = pq.top();
pq.pop();
ll d = top.d;
int u = top.u;
// Type 1 State: Arrived at crossing u normally
if (top.edge_idx == -1) {
if (d > dist[u]) continue;
for (auto& e : adj[u]) {
// Option A: Change only this road's color
if (dist[e.to] > d + e.cost) {
dist[e.to] = d + e.cost;
pq.push({dist[e.to], e.to, 0, -1});
}
// Option B: Change all other roads of the same color
ll cost_all_others = color_sum[u][e.color] - e.cost;
if (dist[e.to] > d + cost_all_others) {
dist[e.to] = d + cost_all_others;
pq.push({dist[e.to], e.to, 0, -1});
}
// Option C: Move to Type 2 state (carrying the color cost)
if (dist_edge[e.id] > d) {
dist_edge[e.id] = d;
pq.push({dist_edge[e.id], e.to, e.color, e.id});
}
}
}
// Type 2 State: Arrived at u, but color 'top.color' was "pre-paid" at previous node
else {
if (d > dist_edge[top.edge_idx]) continue;
for (auto& e : adj[u]) {
if (e.id == top.edge_idx) continue;
if (e.color == top.color) {
ll cost_remaining = color_sum[u][e.color] - e.cost;
if (dist[e.to] > d + cost_remaining) {
dist[e.to] = d + cost_remaining;
pq.push({dist[e.to], e.to, 0, -1});
}
}
}
}
}
if (dist[N] == INF) cout << -1 << endl;
else cout << dist[N] << endl;
return 0;
}
