P16319 [ICPC 2023 Jinan R] 铁路环游

$\textbf{请注意本题不同寻常的空间限制。}$ 《铁路环游》是一款以铁路为主题的德式桌游。在游戏中，玩家需要打出火车卡并在地图上建造铁路。建造出的铁路长度以及玩家是否能连通较远的城市决定了得分，其中需要连通的城市由抽取的车票卡决定。 :::align{center}  BoardGameGeek 用户 @garyjames 拍摄的照片 ::: 考虑游戏的一维版本。有 $(n + 1)$ 座城市排成一行，从左到右编号从 $0$ 到 $n$。对于每个 $1 \le i \le n$，您可以在城市 $(i - 1)$ 与城市 $i$ 之间放置一条铁路以连通它们。 有 $m$ 张车票卡用于奖励玩家连通城市的行为。第 $i$ 张卡可以记为三个整数 $l_i$，$r_i$ 和 $v_i$，表示如果城市 $l_i$ 与 $r_i$ 可以通过铁路连通（也就是说，对于所有 $l_i < j \le r_i$，城市 $(j - 1)$ 和 $j$ 之间都有一条铁路），您将获得 $v_i$ 分。 对于每个 $1 \le k \le n$，计算您恰好放置了 $k$ 条铁路的最大得分。如果没有获得任何奖励，您的得分为 $0$。

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数，对于每组测试数据： 第一行输入两个整数 $n$ 和 $m$（$1 \le n, m \le 10^4$）表示您可以放置铁路的最大数量以及用于奖励的车票卡数量。 对于接下来 $m$ 行，第 $i$ 行输入三个整数 $l_i$，$r_i$ 和 $v_i$（$0 \le l_i < r_i \le n$，$1 \le v_i \le 10^9$）表示如果城市 $l_i$ 与 $r_i$ 可以通过铁路连通，您将获得 $v_i$ 分。 保证所有数据 $n$ 之和与 $m$ 之和均不超过 $10^4$。

每组数据输出一行 $n$ 个由单个空格分隔的整数，其中第 $i$ 个整数表示您恰好放置了 $i$ 条铁路的最大得分。 请不要在行末输出多余空格，否则您的答案可能会被认为是错误的！

令 $(i - 1, i)$ 表示一条位于城市 $(i - 1)$ 和 $i$ 之间的铁路。对于第一组样例数据： - 如果您放置 $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$。