Problem Description

比特国由 $n$ 个城市组成，编号为 $1,2,\cdots,n$。

有 $m$ 条双向道路连接这些城市，第 $i$ 条连通城市 $u_i$ 和城市 $v_i$，通过这条道路需要花费 $t_i$ 的时间。

此外，比特国的人们还可以使用“比特跳跃“来通行于任意两个城市之间。

从城市 $x$ 通过比特跳跃移动到城市 $y$ 需要花费 $k\times (x|y)$ 的时间，其中 $|$ 表示按位或。比特跳跃可以使用任意多次。

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

Input

第一行一个整数 $t\ (1\le t\le 15)$，代表数据组数。

对于每组数据：

第一行三个整数 $n,m,k\ (2\le n\le 10^5,0\le m\le 10^5,0\le k\le 10^6)$，代表城市个数，道路条数，比特跳跃的系数。

接下来 $m$ 行，每行三个整数 $u_i,v_i,t_i\ (1\le u_i,v_i\le n,0\le t_i\le 10^9)$ ，代表一条道路的信息。

**保证所有测试数据的 $\sum n\le 10^6,\sum m\le 10^6$ 。**

Output

对于每组数据，输出一行 $n-1$ 个整数，代表从 $1$ 号城市移动到编号为 $2,3,\dots,n$ 的城市所需的最短时间。

1
6 4 3
1 3 2
1 5 20
2 4 1
4 6 10

9 2 10 15 20