You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小A 最近学习了最短路算法，例如Bellman–Ford，Dijkstra等，他们可以在一定的时间内求解由起点 $S$ 到其他所有点的最短路的长度。“但是对于边数很大的图，就不能直接用最短路算法求解，我们可以考虑这个图是否有什么特殊的性质....”老师小 T 在课上说道。

课后，小 A 的老师小 T 给小 A 留了一个问题：给定 $n$ 个点的图，第 $i(1\le i\le n)$ 个点到第 $j(1\le j\le n)$ 个点有一条单向边，边权是 $|i-j|$ 。除此之外，还有 $m$ 条额外的双向边，第 $i$ 条边连接了第 $x_i$ 和第 $y_i$ 个点，边权为 $z_i$ 。请求出第 $1$ 个点到第 $2\sim n$ 个点的最短路长度。

由于小 A 上课打摆去了，所以自然是不会做的，所以他请你帮帮他。

输入格式

第一行一个正整数 $n,m$，含义如题。

接下来一共 $m$ 行，每行三个整数 $x_i,y_i,z_i$ ，含义如题。

输出格式

一行 $n-1$ 个整数，第 $i$ 个点表示第 $1$ 个点到第 $i+1$ 个点的最短路长度。

样例一

输入

6 4
2 4 4
4 2 2
6 2 2
6 1 2

输出

1 2 3 3 2

数据范围

对于所有数据 $n,m\le 5\times 10^5,0\le z_i\le n$ 。