EOJ-自适应编程学习平台

TheRedStone最近在玩我的世界的一个叫做GTL的科技整合包，游戏中为不同的机器供电是一个麻烦事。TheRedStone搭建的一个自动铂处理产线一共有$n$ ($2\leq n\leq 2e5$)台机器，包含若干台发电机器和生产机器(每台机器要么是发电机器，要么是生产机器)，不同机器之间由$m$根线缆连接。但是相距较远的机器电力传输太慢了，TheRedStone打算利用无线能源仓和无线动力仓减少输电延迟。

在有线传输模式下，电力可以顺着线缆在不同机器之间任意方向流通。对于由延迟为$d$的线缆连接的机器$u$和机器$v$，电能经此线缆从机器$u$传输到机器$v$的延迟是$d$。 在无线输电模式下，发电机器可以向虚空中发送能量，生产机器可以从其所在位置的虚空中提取能量。生产机器$i$从其所在位置的虚空中提取能量有$d_i$的延迟，发电机$j$向生产机器$i$所在的虚空传输能量有$i\oplus j$的延迟。

由于TheRedStone是GTL膏手：

• 他手搓的发电机器的发电量足够大，不需要考虑生产机器接收到的电能是否够用
• 所有机器既可以使用无线输电也可以使用线缆输电(生产机器从虚空获取的能量可以经线缆输给其它机器)
• 每台发电机拥有超高性能，可以同时向其他所有生产机器所在位置的虚空传输能量 现在TheRedStone正忙着推主线任务，他希望你帮他计算产线中每台机器以任意方式接收到发电机电力的最小延迟，方便他改良构式布线。

第一行两个整数$n,\space m$分别表示机器数量和线缆数量$\left(2\leq n\leq 2e5\space,\space 0\leq m\leq \min\left(\frac{n(n-1)}{2},4e5\right)\right)$

第二行$n$个整数，第$i$表示第$i$台机器从虚空提取能量的延迟$d_i(0\leq d_i\leq 1e6)$。当$d_i$为0时表示机器$i$为发电机器，否则为生产机器。保证至少有一台发电机器

接下来$m$行每行三个整数$u,v,w$，表示有一条延迟为$w\left(1\leq w\leq 1e6\right)$的线缆连接机器$u$和机器$v$

输出$n$行，每行包含一个整数，第$i$行表示机器$i$接收到电力的最小延迟(发电机接收延迟为0)