#P18477. Ticket to Ride

Ticket to Ride

Ticket to Ride

《铁路环游》(Ticket to Ride)是一款以铁路为主题的德式桌游。玩家收集并打出火车卡,在地图上修建铁路。修建路线的长度,以及是否连通了抽取的车票卡所指定的远方城市,决定玩家获得的分数。

原题中的铁路环游桌游照片

原照片由 BoardGameGeek 用户 @garyjames 拍摄。

考虑这个游戏的一维版本。有 n+1n+1 座城市排成一行,从左到右编号为 0,1,…,n0,1,\ldots,n。对于每个 1≤i≤n1\le i\le n,你可以在城市 i−1i-1 与城市 ii 之间放置一条铁路,使这两座城市连通。

有 mm 张车票卡,奖励玩家连通城市的行为。第 ii 张卡由三个整数 li,ri,vil_i,r_i,v_i 表示:如果城市 lil_i 与城市 rir_i 通过铁路连通,也就是说,对于每个 li<j≤ril_i<j\le r_i,城市 j−1j-1 与城市 jj 之间都放置了铁路,那么你将获得 viv_i 分。

对于每个 1≤k≤n1\le k\le n,求恰好放置 kk 条铁路时可以获得的最大分数。如果没有获得任何奖励,得分为 00。

输入格式

输入包含多组测试数据。第一行是整数 TT,表示测试数据组数。对于每组测试数据:

第一行包含两个整数 n,mn,m(1≤n,m≤1041\le n,m\le 10^4),分别表示最多可以放置的铁路数量和奖励用的车票卡数量。

接下来 mm 行,第 ii 行包含三个整数 li,ri,vil_i,r_i,v_i(0≤li<ri≤n0\le l_i<r_i\le n,1≤vi≤1091\le v_i\le 10^9),表示城市 lil_i 与城市 rir_i 连通时,该卡奖励 viv_i 分。

保证所有测试数据的 nn 之和不超过 10410^4,所有测试数据的 mm 之和也不超过 10410^4。

输出格式

对于每组测试数据,输出一行 nn 个整数,相邻整数之间用一个空格分隔。第 ii 个整数表示恰好放置 ii 条铁路时的最大分数。

不要在行末输出多余空格,否则你的答案可能被认为不正确。

原样例

2
4 3
0 2 3
3 4 2
0 3 1
3 1
1 3 100
2 3 5 6
0 100 100

样例说明

用 (i−1,i)(i-1,i) 表示城市 i−1i-1 与城市 ii 之间的铁路。第一组测试数据中:

  • 放置 11 条铁路时,可以放置 (3,4)(3,4),获得第二张卡的奖励,答案为 22。
  • 放置 22 条铁路时,可以放置 (0,1)(0,1) 与 (1,2)(1,2),获得第一张卡的奖励,答案为 33。
  • 放置 33 条铁路时,可以放置 (0,1)(0,1)、(1,2)(1,2) 与 (3,4)(3,4),获得第一、第二张卡的奖励,答案为 3+2=53+2=5。
  • 放置全部 44 条铁路时,可以获得全部奖励,答案为 3+2+1=63+2+1=6。