#include<bits/stdc++.h>
#define int long long
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;
const int N = 1e5+5;
const int INF = 1e17;
struct Infor{
int u, c, w;
};
vector<Infor> E[2*N];
map<int,vector<pair<int,int>>> E_color[2*N];
int dp[N];
map<int,int> dp2[N];
map<int,int> sum[N];
int n, m;
/*
Nhận xét:
Do ta có thể đổi màu 1 cạnh thành các màu từ [1, m] mà ta có m cạnh
nên ta luôn có thể đổi màu 1 cạnh sang màu khác mà không trùng với các cạnh còn lại
Gọi dp[u]: là chi phí tối thiểu để đi từ 1 --> u
Xét cạnh (u, v) màu c với chi phí đổi màu là w, khi ta đi từ u --> v ta sẽ có 2 TH
TH1: giữ nguyên màu c của cạnh này, để có thể đi qua ta sẽ đổi màu các cạnh còn lại
nối với đỉnh u mà có cùng màu c
dp[v] = min(dp[v], dp[u] + sum[u][c] - w) ( vì không cần đổi màu cạnh (u, v))
Trong đó:
+ sum[v][c] là tổng chi phí đổi màu của cạnh màu c nối với đỉnh v
TH2: đổi màu c của cạnh khi đi qua, để không trùng với các cạnh khác có cùng màu
dp[v] = min(dp[v], dp[u] + w)
*/
/*
Lúc bấy giờ ở TH2 ta thấy rằng khi ta đổi màu c của cạnh (u, v) thì nó có thể làm giảm chi phí của cạnh (v, k) có màu c.
VD:
Tức nếu từ v ta tiếp tục đi qua một cạnh (v, k) cũng có màu c thì chi phí liên quan đến việc đổi màu
các cạnh màu c tại đỉnh v sẽ được tính lại. Trong đó, chi phí đổi màu của cạnh (u, v) trước đó có thể bị tính trunfgg lại 1 lần nữa
Do đó, khi đổi màu cạnh (u, v), ta cần xem xét ảnh hưởng của nó tới các cạnh (v, k) có cùng màu c nếu ta tiếp tục đi qua chúng
Tuy nhiên việc cập nhật lại chi phí cho toàn bộ các cạnh liên quan khá phức tạp. Từ đây ta có nhận xét quan trọng thứ hai:
Nhận xét 2:
Việc chi phí bị tính lặp chỉ xảy ra khi sau khi đổi màu cạnh (u, v) màu c, ta tiếp tục đi qua một cạnh (v, k) cũng có màu c
Khi đó, để đi qua cạnh (v, k) mà vẫn giữ nguyên màu c, ta phải đổi màu các cạnh khác nối với v có cùng màu c
Tổng chi phí đổi màu này được tính bằng = sum[v][c] - w ( ta lỗi bỏ chi phí w đổi cạnh (v, k) màu c)
Tuy nhiên trong tổng đó đã bao gồm cả chi phí đổi màu của cạnh (u, v) trước đó
==> Để tránh việc tính lại chi phí của cạnh (u, v) màu c nhiều lần, ta chỉ nên cộng chi phí này một lần duy nhất khi đi qua cạnh (v, k) có màu c
và giữ nguyên màu cạnh này
Vì vậy, khi đi qua cạnh (u, v) màu c và quyết định đổi màu cạnh này, ta tạm thời chưa tính chi phí đổi màu
Chi phí sẽ được tính sau, khi ta đi tiếp qua một cạnh (v, k) cũng có màu c.
Lúc đó chi phí cần cộng sẽ là: sum[v][c] - w, còn khi đi (u, v) và ta có đổi màu cạnh này thì ta sẽ không tính chi phí.
==> Nhưng sẽ có nhiều trường hợp như trên với các trọng số khác nhau mà cùng nối đến 1 đỉnh k , do đó ta sẽ gọi quy hoạch động
dp2[u][c]: là chi phí tối thiểu đi đến đỉnh u mà cạnh trước đó có màu c và ta đổi màu cạnh này nhưng
ta tạm chưa tính chi phí
Lúc bấy giờ ta sẽ có thêm TH dp như sau:
TH3: khi ta đi (u, v) có màu c ta thực hiện đổi màu cạnh này nhưng ta tạm chưa tính chi phí, chỉ tính tiếp khi nó đi tiếp
sang (v, k) có màu c.
dp2[v][c] = min(dp2[v][c], dp[u]) ( do ta không tính chi phí đổi màu cạnh này nên chi phí bằng chi phí tối thiểu trước đó đên u
TH4: ta đi qua những cạnh (u, v) có màu c với cchi phí là w
Nhưng trước đó ta đi đến u thông qua một cạnh màu c nhưng chưa tính chi phí đổi màu
dp[v] = min(dp[v], dp2[u][c] + sum[v][c] - w)
Kết hợp thêm 2 TH dp ban đầu ở trên nữa ==> Thì Ta có thể tính nhanh các dp này bằng dijkstra từ đỉnh 1 và có thể AC. Đáp án cuối cùng của ta sẽ là dp[n].
*/
struct Node {
int d, u, type;
bool operator<(const Node &other) const{
return d >other.d;
}
};
void Dijkstra() {
fill(dp, dp+n+1, INF);
priority_queue<Node> pq;
/*
Ta duy trì mỗi node trong pq với các thông tin như sau:
d = Chi phí đến đỉnh u
u = đỉnh đại diện u
type loại kết quả tối ưu khi xét tới đỉnh u là dp hay dp2
+ type = 0 thì chi phí đang xét là dp[u]
+ type != 0 thì chi phí đang xét là chi phí của việc đi qua 1 cạnh màu c tới đỉnh u và chưa tính chi phí đổi
màu canh này , tức dp2[u].
*/
pq.push({0, 1, 0}); // ta xuất phát từ đỉnh 1 với chi phí là 0 và trước đó không có đi qua cạnh màu nào
dp[1] = 0;
while(!pq.empty()) {
Node res = pq.top(); pq.pop();
int u = res.u;
int d = res.d;
int type = res.type;
if(type == 0) {
if(d > dp[u]) continue;
for(Infor &tmp: E[u]) { // duyệt qua các cạnh kề v về với u để tính dp[v] và dp2[v]
int w = tmp.w;
int v = tmp.u;
int c = tmp.c;
// TH1: giữa nguyên cạnh (u, v) có màu c chi phí w , ta sẽ đổi màu những cạnh xung quanh nối với v
// có cùng màu c
if(dp[v] > dp[u] + sum[u][c] - w) {
dp[v] = dp[u] + sum[u][c] - w;
pq.push({dp[v], v, 0});
}
// TH2: đổi màu cạnh (u, v) có màu c chi phí w để ta có thể đi qua
if(dp[v] > dp[u] + w) {
dp[v] = dp[u] + w;
pq.push({dp[v], v, 0});
}
// TH4: ta đi sang cạnh (u, v) có màu c và ta khoang tính chi phí đổi màu , để lượng chi phí đổi màu
// này tính sau
// Lúc bấy giờ dp2[v][c] = dp[u]
// Nhưng nếu dp2[v][c] đã có và tối ưu hơn dp[u] thì ta bỏ qua không xét
if(!dp2[v].count(c) || dp2[v][c] > dp[u]) {
dp2[v][c] = dp[u];
pq.push({dp[v], v, c});
}
}
}
else {
if(d < dp2[u][type]) continue;
// Ta đến đỉnh u thông qua cạnh màu type và ta chưa tính chi phí đổi màu trươc đó
// Lúc bấy giờ ta buộc phải từ u sang những cạnh có màu type và giữ nguyên màu type này
for(pair<int,int> &tmp: E_color[u][type]) { // duyệt qua những cạnh kề v có màu type nối với u
int v = tmp.first;
int w = tmp.second;
// lúc bấy giờ từ u -> v chi phí w để giữ nguyên màu type ta phải đổi màu các cạnh còn lại nối với v có cùng màu type
// chi phí đổi màu = sum[v][type] - w , chi phí mới khi đi sang v từ u này
// dp2[u] + sum[v][type] - w
// nếu dp[v] < dp2[u] + sum[v][type] - w, thì ta pushs vào pq và tối ưu dần.
if(dp[v] > dp2[u][type] + sum[u][type] - w) {
dp[v] = dp2[u][type] + sum[u][type] - w;
pq.push({dp[v], v, 0});
}
}
}
}
}
void solve() {
cin >> n >> m;
for(int i=1; i<=m; i++) {
int u, v, c, p; cin >> u >> v >> c >> p;
E[u].push_back({v, c, p});
E[v].push_back({u, c, p});
E_color[u][c].push_back({v, p}); // dùng 1 vector map để lưu các cạnh có cùng màu với 1 đỉnh
E_color[v][c].push_back({u, p});
sum[u][c] += p; // dùng mảng map để tính chi phí các cạnh có cùng màu c nối với u
sum[v][c] += p;
}
Dijkstra();
cout << (dp[n] == INF ? -1: dp[n]) <<'\n';
}
signed main() {
if(fopen("input.txt", "r")) freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);cin.tie(0);
int T = 1;
// cin >> T;
while(T--) solve();
}
