该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在一个充满奇幻色彩的魔法大陆上，有$n$座由古老魔法守护的城堡，它们各自拥有独特的编号，从$1$到$n$。这些城堡之间，隐藏着m条神秘的双向魔法通道，连接着$u_i,v_i$，但每次通过第$i$条通道都需要消耗$t_i$单位的魔力值。

然而，在这片大陆上，还流传着一种古老的“瞬移魔法”，它允许掌握者无视空间障碍，瞬间从城堡$x$传送到城堡$y$。但使用这种魔法需要消耗$k*(x+y)$的魔力值。

魔法师Gavin，怀揣着对未知世界的好奇与渴望，站在了编号为1的起点城堡前。他计划探索这片大陆的每一个角落，但首先，他需要知道出从起点出发，利用魔法通道和瞬移魔法，到达每一座城堡所需的最少魔力消耗。

于是，他找到了善良聪明的你，希望你能找到最经济的探险路线。

输入格式

第一行输入三个整数 $n,m,k$ ,代表城堡个数，通道条数，“瞬移魔法”的系数。

接下来$m$行，每行三个整数$u_i,v_i,t_i$代表一条通道的信息。

输出格式

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

样例 #1

样例输入 #1

4 3 1
1 2 1
2 3 2
3 4 6

样例输出 #1

1 3 5

提示

数据范围
对于 $100\%$ 数据 $2 \le n,m\le 1e5,0 \le k\le 1e5$。
对于所有$1 \le i \le n$，有 $1 \le u_i,v_i \le n$，$1 \le t_i \le 1e5$。