看到 \(n\le 70\)，想到状压 DP。
首先，显然对于一棵最小生成树，每个轻边连通块内部都是一棵树，轻边连通块缩点后点之间的重边也是一棵树。也就是说，缩点后不存在重边组成的环（包括自环），路径一旦离开了一个轻边连通块就再也不会回来了。
于是先洪水填充求出连通块，设共有 \(k\) 个连通块。设 \(dp_{S,u}\) 表示已经离开（不能再回到）的连通块集合为 \(S\) 时，\(1\sim u\) 的最短路径。初始时 \(dp_{\varnothing,1}=0\)，将转移关系的图建出来之后，每个 \(dp_{S,u}\) 都视为一个节点，原图上的每条边被拆为 \(2^k\) 条边，从源点 \(dp_{\varnothing,1}\) 出发的单源最短路即为 \(dp\) 数组的值。
因此，复杂度是在 \(2^kn\) 个点、\(2^km\) 条边的图上跑 Dijkstra 算法的复杂度，最坏 \(k=n\) 时为 \(\mathcal O(2^nm\log(2^nn))=\mathcal O(2^nmn)\)。
注意到当连通块大小不超过 \(3\) 时，内部一定可以通过不超过 \(2\) 条轻边到达，而出连通块再回来至少要走 \(2\) 条重边，这种情况自然不优，我们可以不用处理所有大小不超过 \(3\) 的连通块。因此，我们要处理的连通块数 \(k\le\lfloor\frac{n}{4}\rfloor\)。
时间复杂度变为 \(\mathcal O(2^{\frac{n}{4}}m\log(2^{\frac{n}{4}}n))=\mathcal O(2^{\frac{n}{4}}mn)\)，可以通过本题。代码想清楚还是挺好写的。
边权只有两种，可以开两个队列进行 BFS 优化成 \(\mathcal O(2^{\frac{n}{4}}m)\)，但我没有写。甚至还有 \(\mathcal O(2^{\sqrt{n\log n}}\operatorname{poly}(n,m))\) 的解法。
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
uniform_int_distribution<int> dist(L, R);
return dist(rnd);
}
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
const int N = 75, M = 205, K = 18;
int n, m, a, b, e[N][N], vis1[N], vis2[N], id[N], sz[N], cnt, dim, dp[N][1<<K], vis[N][1<<K];
int dfs1(int u) {
vis1[u] = 1;
int sz = 1;
rep(v, 1, n) if(e[u][v] == a && !vis1[v]) sz += dfs1(v);
return sz;
}
void dfs2(int u, int cnt) {
vis2[u] = 1;
id[u] = cnt;
++sz[cnt];
rep(v, 1, n) if(e[u][v] == a && !vis2[v]) dfs2(v, cnt);
}
int main() {
scanf("%d%d%d%d", &n, &m, &a, &b);
rep(i, 1, m) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
e[u][v] = e[v][u] = w;
}
rep(i, 1, n) if(!vis1[i]) if(dfs1(i) >= 4) dfs2(i, cnt++);
dim = cnt;
memset(vis1, 0, sizeof(vis1));
rep(i, 1, n) if(!vis1[i]) if(dfs1(i) < 4) dfs2(i, cnt++);
memset(dp, 0x3f, sizeof(dp));
priority_queue<tuple<int, int, int>> q;
dp[1][0] = 0;
q.emplace(0, 1, 0);
while(!q.empty()) {
int _, u, S;
tie(_, u, S) = q.top(); q.pop();
if(vis[u][S]) continue;
vis[u][S] = 1;
rep(v, 1, n) {
if(!e[u][v]) continue;
int Sn = S;
if(e[u][v] == b) {
if(id[u] == id[v] || id[v] < dim && ((S >> id[v]) & 1)) continue;
if(id[u] < dim) Sn |= 1 << id[u];
}
if(dp[v][Sn] > dp[u][S] + e[u][v]) {
dp[v][Sn] = dp[u][S] + e[u][v];
q.emplace(-dp[v][Sn], v, Sn);
}
}
}
rep(i, 1, n) {
printf("%d%c", *min_element(dp[i], dp[i]+(1<<dim)), " \n"[i==n]);
}
return 0;
}