题目描述

有一支流行乐队要在$\red{A}$国开演唱会，$\red{A}$国由$\red{n}$个城市和$\red{m}$条道路组成，每条道路有一个花费。

现在这$\red{n}$个城市的人都想去听演唱会，但每个城市的票价不同，于是这些人就想是否能去其他城市听演唱会 更便宜。

（去别的城市需要路费，且需要返程，可以描述为下式）

$\red{\text{~~~n}\\{min~2d(i,j)+a_j}\\{j=1}}$

其中$\red{d(i,j)}$表示从$\red{i}$到$\red{j}$的最小花费。

现在请你计算对于$\red{i=1,2,...,n，}$第$\red{i}$个城市的人去参加演唱会的最小花费。

输入格式

第一行两个整数$\red{n,m}$表示城市数和道路数。

接下来$\red{m}$行每行三个整数$\red{x_i,y_i,z_i}$表示存在一条连接$\red{x}$和$\red{y}$的花费为$\red{z}$的双向道路。

输出格式

共一行，$\red{n}$个整数表示每个城市的人去看演唱会的最小花费。

样例

输入样例

4 2
1 2 4
2 3 7
6 20 1 25

输出样例

6 14 1 25

提示

对于$\red{30\%}$的数据，$\red{1<=n,m<=10^3}$。

对于$\red{100\%}$的数据，$\red{1<=n,m<=2\times 10^5,1<=w_i,a_i<=10^{12}}$