TAIKULA 是一个复杂的星系，由 $n$ 个不同的恒星组成，编号从 $0$ 到 $n-1$，并通过 $m$ 条有向星轨相互连接。我们的故事围绕星穹列车的勇敢船员展开，特别是三月七和丹恒，他们被指派在 TAIKULA 执行运送珍稀遗器的关键任务。他们的任务因空间站突如其来的崩坏袭击而中断。幸运的是，三月七和丹恒与首席研究员艾丝妲以及防卫科负责人阿兰一起，成功击退了袭击者。然而，这些崩坏遭遇现在已成为星轨沿线一种不幸但频繁的干扰，造成了各种损失。作为回应，艾丝妲承担了估算每条星轨相关潜在损失的任务，并在她的地图上为它们分配了整数值。值得注意的是，这些整数可能是负数，因为一些较弱但富有的崩坏可能会被击败，从而使星穹列车获得有价值的装备或材料。

TAIKULA 内任何商业运输的标准协议都涉及从一颗恒星 $x$ 出发，穿过其他（至少一颗）恒星，并最终返回原始恒星 $x$ 进行必要的维护。在此次运输过程中，恒星和星轨可能会被多次访问，包括起始恒星。艾丝妲热衷于尽可能减少每次从起始恒星出发所产生的损失。

有趣的是，崩坏在 TAIKULA 中表现出一种奇特的习惯。在运输过程中，它们只掠夺奇数编号的货物，并且当损失为偶数时，它们的攻击性会呈指数级上升。这促使艾丝妲寻求你这位拥有星核之力的开拓者的专业知识。你的任务是为每颗起始恒星规划一条运输路线，使其产生的奇数损失尽可能小。为了加快进程，你只需要计算出每颗起始恒星的最小奇数损失。

输入格式

第一行包含两个整数 $n, m$ ($1 \le n \le 1000, 1 \le m \le 10^4$)，表示恒星的数量和星轨的数量。

接下来的 $m$ 行，每行包含 3 个整数 $x_i, y_i, w_i$ ($0 \le x_i, y_i < n, |w_i| \le 10^7$)，标识一条从恒星 $x_i$ 到恒星 $y_i$ 的有向星轨，其损失为 $w_i$。

输出格式

输出应包含 $n$ 行。第 $i$ 行应标识第 $(i-1)$ 颗起始恒星的最小奇数损失。如果不存在奇数损失的运输路线，输出 Battle with the crazy Honkai。否则，如果最小奇数损失是有限的，输出该损失。如果它是无限的，输出 Haha, stupid Honkai。

样例

样例输入 1

2 2
0 1 1
1 0 1

样例输出 1

Battle with the crazy Honkai
Battle with the crazy Honkai

样例输入 2

2 2
0 1 0
1 0 1

样例输出 2

1
1

样例输入 3

2 2
0 1 -1
1 0 0

样例输出 3

Haha, stupid Honkai
Haha, stupid Honkai

样例输入 4

2 2
0 1 2
1 0 -1

样例输出 4

1
1