You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

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

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

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

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

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

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

——唯一……人类除外。

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

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

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

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

「所以我要以唯一神的身分，给予你们名号——人类种（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$ 秒不意味着可以为所欲为。