Description

小A现在想用m条彩灯去装饰家中的走廊，走廊可以视作一个[1，n]的区间，每一条彩灯都能覆盖一 个子区间，并且有一个特定的美观程度。 然而为了降低装饰的难度，彩灯能够覆盖的区间两两之间只有包含和不相交的关系，同时为了避免光污 染，他希望每个[1，n]中的点至多被k条彩灯覆盖。 现在小A希望你能告诉他，k= 1，2，..., m时，选出的彩灯的最大美观程度之和时多少。

Input Format

第一行两个整数n，m表示区间的长度与彩灯的数量。 接下来m行，每行三个整数li,ri,ai表示一条彩灯能够覆盖的区间以及它的美观程度。

Output Format

输出一行 𝑛 个整数，第 𝑖 个数表示 𝑙 = 𝑖 时的最大美观程度。

Sample

Sample Input

25 6
1 2 10
2 3 10
1 3 21
3 4 10
4 5 10
3 5 19

Sample Output

41 80 80 80 80 80

Hint

对于 25% 的数据，m ≤ 5000 对于 45% 的数据，n,m ≤ 5000 对于另外 25% 的数据，所有ai相同 对于 100% 的数据，1 ≤ l 𝑖 ≤ 𝑟 𝑖 ≤ n,m ≤ 300000,𝑎 𝑖 ≤ 1000000000