题目背景

——喂——我们再来玩游戏吧……下次我一定会赢你的……

——和休比两个人一起……绝对……要……

回想起那件事，少年——仅仅两人的相信所诞生的神灵种。

他就是里克在年幼的那一日，看着黑暗深处所想像出的最强游戏玩家。

他自信、大胆，而且——浮现出不服输的笑容，举起『星杯』。

---

这个世界的所有知性生命体都是神灵种所创。

——唯一……人类除外。

「不被任何人所创，不受任何人的期望，不被任何人祈愿。只是凭借自己的意志，从野兽演化到用双足站立，以至于得到知性的唯一种族——无名种族——人类。」

只有他们成功终结无谓、无为、无聊的战争。

就算结果是肮脏的比赛——也只有他们。

要将他们与普通的野兽并列而语吗？——断然不可吧。

「所以我要以唯一神的身分，给予你们名号——人类种（immunity）……『免疫（immunity）』。」

不断学习，得到耐性，绝不停止抵抗，即便到了最后一人也不放弃，终于有如星球本身的免疫机能一般，阻止了拥有愚蠢疾病的人们。

所谓进化的概念，对于将无限可能性——藏于一身的种族，那是相当适合的名字。

然后特图缓缓地继续笑着。

「好了——继续游戏吧。」

因为长将和而被和局，这样也很不愉快，所以就照他们所望——

「大家一起玩乐，谁也不会死，我会准备那样的游戏，等着你们。」

这个世界并没有——轮回转生。

即使如此，他们到最后仍持续相信的『下次』——我也相信看看。

「好了——那么……」

这么说着，最弱的、最后的神灵种，高举了『星杯』。

以遍及天上地下，传达给每一个人的声音告知：

『自称拥有知性的【十六种族】啊——！』

——然后没有被传颂的神话——

迈向被口耳相传的神话，也就是——

继承遗志们的正式仪式。

无视十六种族的同意。

基于唯一神之宝座所定的『十条盟约』。

来吧，景仰吧。今天，从这一日开始，世界改变了。

——【向盟约宣誓】——！

题目描述

「圣战」期间，作为「幽灵」小队队长的里克得到了一份「森精种」所精细绘制的大陆地图。

地图被里克抽象为 $n$ 座主要城市和 $m$ 条连接这些城市之间的通道。第 $i(1 \leq i \leq m)$ 条通道能从第 $u_i$ 座城市花费 $a$ 单位时间走向第 $v_i$ 座城市，通道是双向的。

作为「遗志体」的同种「机凯种」，它们决定协助里克完成休比的遗志。具体地，它们复制了一种新型的魔法：如果从第 $x$ 座城市 仅走最短路径 可以恰好在 $2a$ 时间内到达第 $y$ 座城市，那么也可以在 $b$ 时间内通过「传送术式」从第 $x$ 座城市到达第 $y$ 座城市。

现在里克想要从第 $1$ 座城市分别前往第 $2 \sim n$ 座城市，请你帮忙求出里克最少在路上需要花费多少时间。

保证里克可以到达每一座城市。

输入格式

从标准输入中读入数据。

第一行，四个整数 $n, m, a, b$。

接下来 $m$ 行，每行两个整数 $u_i, v_i$。

输出格式

输出到标准输出。

一行 $n - 1$ 个整数，其中第 $i$ 个表示终点为 $i + 1$ 的答案。

样例

5 5 3 2
1 2
1 3
2 3
3 4
4 5

3 3 2 5

见选手目录下的 dream/dream2.in

见选手目录下的 dream/dream2.ans

数据规模与约定

本题采用捆绑测试。

• Subtask 1（9 pts）：$n \leq 10$，$m \leq 15$。
• Subtask 2（19 pts）：$n \leq 5000$，$m \leq 1.5\times 10^4$。
• Subtask 3（23 pts）：$a = b$。
• Subtask 4（49 pts）：无特殊限制。

对于 $100\%$ 的数据，保证 $1 \leq n \leq 5\times 10^4$，$n - 1 \leq m \leq 1.5 \times 10^5$，$1 \leq a, b \leq 5\times 10^3$，保证图联通。

温情提示

时间限制 $5$ 秒不意味着可以为所欲为。