该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

新日暮里有$N$座城市，从$1$到$N$标号，其中有$M$对城市有有向道路连接，每条道路有一定的长度。并且，从被称为首都的$1$号城市出发可以到达新日暮里的所有城市——虽然很有可能没法回到起点。
正常情况下，一条路径的长度就是经过它的代价。不过因为住在新日暮里的居民们都有着深黑幻想，所以经过一条由$E$条边组成的、总长度为$W$路径，代价是$E \times W$。
请你为王找出从$1$出发，分别到达$[2, N]$中的点所需要的最小代价。

输入格式

第一行两个正整数$N, M$。
从第二行起$M$行，每行三个整数$u_i, v_i, w_i$，表示一条边的起点、终点，和这条边的长度。
保证不会存在两条$u, v$均相同的边。

输出格式

$N - 1$行，每行一个整数表示$Cost_{i + 1}$，即到达$i + 1$号点的最小代价。

样例输入

3 3
1 2 2
2 3 1
1 3 4

样例输出

2
4

样例解释

$1 \rightarrow 2: 2 \times 1 = 2$
$1 \rightarrow 3: 4 \times 1 = 4$
虽然$1 \rightarrow 2 \rightarrow 3$的距离更短，但是由于经过了两条边，代价为$3 \times 2 = 6$。

约定与限制

一共十组数据，编号从$1$到$10$。
对于第$i$组数据，$N \leq 2 ^ i$。
对于所有数据，$M \leq min(N \times (N - 1), 2333), 0 \lt w_i \leq 2333$