Description

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

这n 个城市的人都想去听演唱会，但每个城市的票价不同，于是这些人就想是否能去其他城市听演唱会

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

min 2d(i,j)+aj     (  j从1到n )

其中d(i,j)表示从i到j的最小消费

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

Format

Input

第一行两个整数n，m表示城市数和道路数

接下来m行每行三个整数xi,yi,zi，表示存在一条连接x和y的花费为z的双向道路

Output

共1行

Samples

4 2

1 2 4

2 3 7

6 20 1 25

6 14 1 25

3 3

1 2 1

2 3 1

1 3 1

30 10 20

12 10 12

Limitation

1s, 1024KiB for each test case.

对于30%的数据， 1=<n,m<=1000

对于100%的数据， 1=<n,m<=2*10^5 , 1=<wi,ai<=10^12