题目描述

给定一个有向图，包含 N 个顶点，编号为 1 到 N。图中的边以压缩形式给出。每一组边由三个整数 (u, l, r) 描述，表示：

对于区间 [l, r] 中的每个顶点 v，都添加一条从 u 指向 v 的有向边，其边权为：

你的任务是求出从顶点 1 到每个其他顶点的最短路。

输入格式

第一行输入两个整数 N 和 M，分别表示顶点个数和压缩边组数。

接下来 M 行，每行输入三个整数 u、l、r，描述一组边。

输出格式

输出 N 个整数，其中第 i 个整数表示从顶点 1 到顶点 i 的距离。

如果某个顶点无法从顶点 1 到达，输出 -1。

数据范围

• 1 \le N \le 10^5
• 1 \le M \le 2 \times 10^5
• 1 \le u, l, r \le N
• 对于每组边，保证 l \le r

子任务

• 在 40% 的测试中，N, M \le 2000
• 在 60% 的测试中，N \le 4000

样例

输入

10 5
1 1 2
1 8 9
1 7 8
9 3 4
9 3 4

输出

0 2 3 4 -1 -1 1 1 2 -1

样例解释

在样例中共有 10 个顶点，5 组压缩边。

例如，第一组 1 1 2 表示加入如下两条边：

• 从顶点 1 到顶点 1，边权为 1
• 从顶点 1 到顶点 2，边权为 2

将所有边加入后，求从顶点 1 到每个顶点的最短路。

例如，到顶点 2 的距离为 2，到顶点 4 的距离为 4。对于无法从顶点 1 到达的顶点，输出 -1。