题目描述

比特国由 $N$ 个城市构成，编号为 $1,2,\dots,N$。

有 $M$ 条双向道路连接这些城市，第 $i$ 条连通城市 $U_i$ 和城市 $V_i$，通过这条道路需要花费 $W_i$ 的时间。

此外，比特国的人们还可以使用“比特跳跃“来通行于任意两个城市之间。比特跳跃所需的时间取决于两个常数，$S$和$K$，两者均为整数。对于从城市 $x$ 跳跃到城市 $y$ ：

• $S=1$：传送需要$K \times (x \& y)$单位时间($\&$表示按位与(bitwise AND))。
• $S=2$：传送需要$K \times (x \oplus y)$单位时间($\oplus$表示按位异或(bitwise XOR))。
• $S=3$：传送需要$K \times (x|y)$单位时间($|$表示按位或(bitwise OR))。

请你计算从 1 号城市移动到每个城市所需的最短时间。

输入格式

从 jump.in 文件读入数据。

第一行四个整数：$N, M, S, K$。

接下来的 $M$ 行中，第 $i$ 行包含三个整数：$U_i, V_i, W_i$，描述第 $i$ 条双向道路。

输出格式

输出到 jump.out 文件。

输出一行 $N - 1$ 个整数，其中第 $i$ 个整数是从 $1$ 号城市旅行到 $i + 1$ 号城市所需的最短时间。

样例

5 3 2 10
1 3 10
2 3 100
4 5 5

20 10 45 40

5 3 3 10
1 3 10
2 3 100
4 5 5

30 10 50 50

2 0 1 1

0

大样例

点击链接 ex_jump4.in 和 ex_jump4.out 下载大样例 4 的输入数据和输出数据。

点击链接 ex_jump5.in 和 ex_jump5.out 下载大样例 5 的输入数据和输出数据。

点击链接 ex_jump6.in 和 ex_jump6.out 下载大样例 6 的输入数据和输出数据。

数据范围

对于所有测试数据，

$2 \leq N \leq 10^5$，

$0 \leq M \leq 10^5$，

$1 \leq S \leq 3$，

$0 \leq K \leq 10^6$，

对于所有 $1 \leq i \leq M$，$1 \leq U_i, V_i \leq N$，

对于所有 $1 \leq i \leq M$，$U_i \neq V_i$，

对于所有 $1 \leq i \leq M$，$0 \leq W_i \leq 10^9$。

子任务	分数	附加约束条件
$1$	$19$	$N, M \leq 800$
$2$	$9$	$S = 1$, $N$ 是 2 的整数次幂
$3$	$11$	$S = 1$
$4$	$30$	$S = 2$
$5$	$31$	$S = 3$