L. Ticket to Ride
time limit per test
3 seconds
memory limit per test
128 megabytes
input
standard input
output
standard output

Please note the UNUSUAL MEMORY LIMIT of this problem.

Ticket to Ride is a railway-themed German-style board game. In the game, players collect and play train cards to build railroads across the map. Points are earned based on the length of the built routes, and whether the player can connect distant cities which are determined by drawing ticket cards.

Photo by @garyjames on BoardGameGeek

Consider a one-dimensional version of the game. There are $$$(n + 1)$$$ cities arranged in a row, numbered from $$$0$$$ to $$$n$$$ from left to right. For each $$$1 \le i \le n$$$, you can connect city $$$(i - 1)$$$ and city $$$i$$$ by placing a railroad between them.

There are $$$m$$$ ticket cards which reward the player for connecting cities. The $$$i$$$-th card can be represented by three integers $$$l_i$$$, $$$r_i$$$ and $$$v_i$$$, indicating that if city $$$l_i$$$ and $$$r_i$$$ are connected through railroads (that is, for all $$$l_i \lt j \le r_i$$$, there is a railroad placed between city $$$(j - 1)$$$ and $$$j$$$), you will gain $$$v_i$$$ points.

For each $$$1 \le k \le n$$$, calculate the maximum points you can gain if you place exactly $$$k$$$ railroads. If you fail to gain any reward then you get $$$0$$$ points.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^4$$$) indicating the maximum number of railroads you can place and the number of ticket cards for rewarding.

For the following $$$m$$$ lines, the $$$i$$$-th line contains three integers $$$l_i$$$, $$$r_i$$$ and $$$v_i$$$ ($$$0 \le l_i \lt r_i \le n$$$, $$$1 \le v_i \le 10^9$$$) indicating that if city $$$l_i$$$ and $$$r_i$$$ are connected through railroads, you will gain $$$v_i$$$ points.

It's guaranteed that neither the sum of $$$n$$$ nor the sum of $$$m$$$ of all test cases will exceed $$$10^4$$$.

Output

For each test case output one line containing $$$n$$$ integers separated by a space, where the $$$i$$$-th integer indicates the maximum points you can gain if you place exactly $$$i$$$ railroads.

Please, DO NOT output extra spaces at the end of each line, or your solution may be considered incorrect!

Example
Input
2
4 3
0 2 3
3 4 2
0 3 1
3 1
1 3 100
Output
2 3 5 6
0 100 100
Note

Let $$$(i - 1, i)$$$ be a railroad between city $$$(i - 1)$$$ and $$$i$$$. For the first sample test case:

  • If you place $$$1$$$ railroad, you can place $$$(3, 4)$$$, then get the second reward. The answer is $$$2$$$.
  • If you place $$$2$$$ railroads, you can place $$$(0, 1)$$$ and $$$(1, 2)$$$, then get the first reward. The answer is $$$3$$$.
  • If you place $$$3$$$ railroads, you can place $$$(0, 1)$$$, $$$(1, 2)$$$ and $$$(3, 4)$$$, then get the first and the second reward. The answer is $$$3 + 2 = 5$$$.
  • If you place all $$$4$$$ railroads you can get all rewards. The answer is $$$3 + 2 + 1 = 6$$$.