U165036 2021.6.4prize

XYX 在 CChO(全国化学奥林匹克竞赛)比赛中获得了大奖，奖品是一张特殊的机票。 使用这张机票，可以在任意一个国家内的任意城市之间的免费飞行，只有跨国飞行时才 会有额外的费用。XYX 获得了一张地图，地图上有城市之间的飞机航班和费用。已知从 每个城市出发能到达所有城市，两个城市之间可能有不止一个航班。一个国家内的每两 个城市之间一定有不止一条飞行路线，而两个国家的城市之间只 有一条飞行路线。XYX 想知道，从每个城市出发到额外费用最大的城市，以便估算出出行的费用，请你帮助他。 当然，你不能通过乘坐多次一个航班增加额外费用， 也就是必须沿费用最少的路线飞 行。

无

第一行，两个整数 $N,M$，表示地图上有 $N$ 个城市，$M$ 条航线。 接下来 $M$ 行，每行三个整数 $a,b,c$，表示城市 $a,b$ 之间有一条费用为 $c$ 的航线。

共 $N$ 行，第 $i$ 行为从城市 $i$ 出发到达每个城市额外费用的最大值。

样例说明： 有四个国家，包含的城市分别为 ${1,2,3},{4},{5},{6}$。 从城市 $1$ 出发到达城市 $6$，乘坐 $(1,3)(3,6)$ 两个航班费用最大， $(1,3)$ 在国内为免费航班，$(3,6)$ 的费用为 $4$，所以从 $1$ 出发的最 大费用为 $4$。 对于 40% 的数据 $1