#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
const long long INF = 1e18; // Sử dụng giá trị lớn cho vô cùng
struct Road {
int u, v, id; // id là chỉ số của con đường trong mảng roads_data
int initial_color;
int cost_to_change;
};
struct State {
long long cost;
int node;
bool operator>(const State& other) const {
return cost > other.cost;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
cin >> N >> M;
vector<Road> roads_data(M);
// adj[node] lưu danh sách các cặp {neighbor_node, road_id}
vector<vector<pair<int, int>>> adj(N + 1);
for (int i = 0; i < M; ++i) {
int u, v, c, p;
cin >> u >> v >> c >> p;
roads_data[i] = {u, v, i, c, p};
adj[u].push_back({v, i});
adj[v].push_back({u, i}); // Đường đi hai chiều
}
vector<long long> dist(N + 1, INF);
priority_queue<State, vector<State>, greater<State>> pq;
dist[1] = 0;
pq.push({0, 1});
while (!pq.empty()) {
State current = pq.top();
pq.pop();
long long current_cost = current.cost;
int u = current.node;
if (current_cost > dist[u]) {
continue;
}
// Duyệt qua tất cả các màu có thể (1 đến M)
// Giả sử chúng ta muốn nói màu 'target_color' từ node 'u'
for (int target_color = 1; target_color <= M; ++target_color) {
long long cost_to_make_move = 0;
int potential_next_node = -1; // Node mà chúng ta sẽ đến nếu nói target_color
bool possible_move = true; // Có thể thực hiện nước đi này không
// Liệt kê tất cả các con đường xuất phát từ 'u'
vector<int> roads_from_u_indices;
for (auto& edge : adj[u]) {
roads_from_u_indices.push_back(edge.second);
}
// Bước 1: Tìm con đường tiềm năng duy nhất để đi
// Nếu có nhiều đường màu target_color, hoặc đường đó không dẫn đến một node duy nhất,
// thì chúng ta phải thay đổi màu của các đường thừa.
// Cách tính chi phí cho mỗi màu 'target_color' từ 'u':
// Chúng ta muốn có duy nhất một con đường 'X' xuất phát từ 'u' có màu 'target_color',
// và các con đường khác đều không có màu 'target_color'.
vector<pair<int, int>> roads_with_target_color_from_u; // {road_idx, neighbor_node}
for (int road_idx : roads_from_u_indices) {
Road& r = roads_data[road_idx];
int neighbor_node = (r.u == u) ? r.v : r.u;
if (r.initial_color == target_color) {
roads_with_target_color_from_u.push_back({road_idx, neighbor_node});
}
}
// Trường hợp 1: Không có con đường nào ban đầu có màu target_color
// Chúng ta phải chọn một con đường và thay đổi màu của nó.
// Để tối ưu, chúng ta sẽ chọn con đường có chi phí thay đổi thấp nhất.
if (roads_with_target_color_from_u.empty()) {
long long min_change_cost_to_create_path = INF;
int best_road_idx_to_change = -1;
for (int road_idx : roads_from_u_indices) {
Road& r = roads_data[road_idx];
if (r.cost_to_change < min_change_cost_to_create_path) {
min_change_cost_to_create_path = r.cost_to_change;
best_road_idx_to_change = road_idx;
}
}
if (best_road_idx_to_change != -1) {
cost_to_make_move += min_change_cost_to_create_path;
Road& best_r = roads_data[best_road_idx_to_change];
potential_next_node = (best_r.u == u) ? best_r.v : best_r.u;
} else {
possible_move = false; // Không có đường nào để thay đổi màu
}
}
// Trường hợp 2: Có một hoặc nhiều con đường ban đầu có màu target_color
else {
// Nếu có 1 con đường ban đầu có màu target_color
if (roads_with_target_color_from_u.size() == 1) {
potential_next_node = roads_with_target_color_from_u[0].second;
// Không cần thay đổi màu của nó, chi phí là 0 cho đường này
}
// Nếu có nhiều hơn 1 con đường ban đầu có màu target_color
else {
// Tìm con đường có chi phí thay đổi thấp nhất để giữ lại làm màu target_color,
// và thay đổi màu của các con đường còn lại.
long long min_cost_to_keep_one = INF;
int best_road_to_keep_idx = -1;
int best_road_to_keep_neighbor = -1;
for (auto& p : roads_with_target_color_from_u) {
int road_idx = p.first;
int neighbor = p.second;
Road& r = roads_data[road_idx];
long long current_temp_cost = 0;
for (auto& other_p : roads_with_target_color_from_u) {
int other_road_idx = other_p.first;
if (other_road_idx != road_idx) {
current_temp_cost += roads_data[other_road_idx].cost_to_change;
}
}
if (current_temp_cost < min_cost_to_keep_one) {
min_cost_to_keep_one = current_temp_cost;
best_road_to_keep_idx = road_idx;
best_road_to_keep_neighbor = neighbor;
}
}
cost_to_make_move += min_cost_to_keep_one;
potential_next_node = best_road_to_keep_neighbor;
}
}
// Nếu có một nước đi hợp lệ với chi phí đã tính
if (possible_move && potential_next_node != -1) {
if (current_cost + cost_to_make_move < dist[potential_next_node]) {
dist[potential_next_node] = current_cost + cost_to_make_move;
pq.push({dist[potential_next_node], potential_next_node});
}
}
}
}
if (dist[N] == INF) {
cout << -1 << endl;
} else {
cout << dist[N] << endl;
}
return 0;
}
