考虑一条 \(1 \to i\) 的路径是否在最小生成树上。
称边权为 \(a\) 的边为轻边，边权为 \(b\) 的边为重边。
轻边若不成环则一定在最小生成树上，因此先把轻边合并，这样形成了若干连通块。
那么如果两点在一个连通块，它们只能通过轻边互达。
同时，因为是树上路径，所以不会走出一个连通块再走回这个连通块。
于是可以想到设 \(f_{S, u}\) 为当前已经经过的连通块集合，和当前所在的点。
因为 \(f_{S, u}, f_{S, v}\) 可以互相转移，所以用最短路的方式计算。
但是有个问题。连通块个数可能很多，无法状压。
但是注意到，若连通块点数 \(\le 3\)，那么任意两点都能通过不超过两条轻边互达，所以通过重边走出去再走回来一定不优。所以就可以直接不记录这些连通块。
那么因为要记录的连通块点数 \(\ge 4\)，所以连通块个数 \(\le \frac{n}{4}\)。
所以复杂度就变成了 \(O(2^{\frac{n}{4}} m \log (2^{\frac{n}{4}} m))\)。
code
// Problem: D. Abandoning Roads
// Contest: Codeforces - Codeforces Round 556 (Div. 1)
// URL: https://codeforces.com/problemset/problem/1149/D
// Memory Limit: 512 MB
// Time Limit: 5000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 210;
const int maxm = (1 << 17) + 50;
ll n, m, A, B, fa[maxn], tot, id[maxn], sz[maxn];
ll f[maxm][75];
vector<pii> G[maxn];
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
inline void merge(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
fa[x] = y;
sz[y] += sz[x];
}
}
struct node {
ll S, u, d;
node(ll a = 0, ll b = 0, ll c = 0) : S(a), u(b), d(c) {}
};
bool vis[maxm][75];
inline bool operator < (const node &a, const node &b) {
return a.d > b.d;
}
void solve() {
scanf("%lld%lld%lld%lld", &n, &m, &A, &B);
for (int i = 1; i <= n; ++i) {
fa[i] = i;
sz[i] = 1;
}
while (m--) {
ll u, v, d;
scanf("%lld%lld%lld", &u, &v, &d);
G[u].pb(v, d);
G[v].pb(u, d);
if (d == A) {
merge(u, v);
}
}
for (int i = 1; i <= n; ++i) {
if (fa[i] == i) {
if (sz[i] > 3) {
id[i] = tot++;
} else {
id[i] = -1;
}
}
}
for (int i = 1; i <= n; ++i) {
id[i] = id[find(i)];
}
mems(f, 0x3f);
f[id[1] == -1 ? 0 : (1 << id[1])][1] = 0;
priority_queue<node> pq;
pq.emplace(id[1] == -1 ? 0 : (1 << id[1]), 1, 0);
while (pq.size()) {
int S = pq.top().S, u = pq.top().u;
pq.pop();
if (vis[S][u]) {
continue;
}
vis[S][u] = 1;
for (pii p : G[u]) {
ll v = p.fst, d = p.scd;
if (id[v] != -1 && id[u] != id[v] && (S & (1 << id[v]))) {
continue;
}
if (find(u) == find(v) && d == B) {
continue;
}
int T = S | (id[v] == -1 ? 0 : 1 << id[v]);
if (f[T][v] > f[S][u] + d) {
f[T][v] = f[S][u] + d;
if (!vis[T][v]) {
pq.emplace(T, v, f[T][v]);
}
}
}
}
for (int i = 1; i <= n; ++i) {
ll ans = 9e18;
for (int S = 0; S < (1 << tot); ++S) {
ans = min(ans, f[S][i]);
}
printf("%lld ", ans);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}