题目描述

有 $n$ 条线段依次相连，顶点编号 $0\sim n$ ，第 $i$ 条线段连接顶点 $i-1$ 和 $i$ 。

你可以选一些线段将它们涂色，其他线段未涂色。有 $m$ 个需求，第 $i$ 个需求是用涂色的线段将顶点 $l_i$ 到和顶点 $r_i$ 连通，若该需求被满足，则可以获得 $v_i$ 的收益。

对 $k=1,2,\cdots,n$ 分别计算：恰好将 $k$ 条线段涂色的情况下最多获得多少收益。

输入格式

本题包含多组测试数据。第一行一个整数 $T$ ，表示数据组数。

每组数据：
第一行两个整数 $n,m$ ，表示线段的数量和需求的数量。
接下来 $m$ 行，每行三个整数 $l_i,r_i,v_i$ ，表示一个需求。

输出格式

每组数据输出一行，包含 $n$ 个整数，依次是 $k=1,2,\cdots,n$ 时的答案。

样例1

样例输入

2
4 3
0 2 3
3 4 2
0 3 1
3 1
1 3 100

样例输出

2 3 5 6
0 100 100

样例解释

• 若涂 $1$ 条线段，选 $(3,4)$ ，总收益为 $2$ ；
• 若涂 $2$ 条线段，选 $(0,1)$ 和 $(1,2)$ ，总收益为 $3$ ；
• 若涂 $3$ 条线段，选 $(0,1)$ ， $(1,2)$ 和 $(3,4)$ ，总收益为 $3+2=5$ 。
• 若涂 $4$ 条线段，全选，总收益为 $3+2+1=6$ 。

样例2~5

见附加的样例文件，依次符合每个子任务的限制。

数据范围

所有数据：

• $1\leq n,m\leq 10^4$
• $0\leq l_i<r_i\leq n$
• $1\leq v_i\leq 10^9$
• $\sum n\leq 10^4$
• $\sum m\leq 10^4$

子任务分布：

• 子任务1 (10分): $\sum n \leq 20$ ， $\sum m \leq 20$
• 子任务2 (20分): $\sum n \leq 300$ ， $\sum m \leq 300$
• 子任务3 (30分): $\sum n \leq 1500$ ， $\sum m \leq 1500$
• 子任务4 (40分): 无特殊限制