小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 个点的最短路长度。

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