题目描述

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

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

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

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

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

输入格式

第一行一个整数 $T$ ($1≤T≤15$)，代表数据组数。

对于每组数据：

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

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

保证所有测试数据的 $∑n≤10^6,∑m≤10^6$。

输出格式

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

输入样例

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

输出样例

9 2 10 15 20