Description

There are $n$ car wash shops arranged in a row from left to right. Each shop has a positive integer price $p_i$. There are $m$ customers. The $i$-th customer will drive past shops from the $a_i$-th to the $b_i$-th, inclusive, and will choose the cheapest shop among these to buy one wash. However, if this cheapest price is greater than $c_i$, then this person does not buy a wash. Assign a price to each shop so that the total amount spent by all customers is maximized.

Input Format

The first line contains two positive integers $n, m$ ($1 \le n \le 50$, $1 \le m \le 4000$).
The next $m$ lines each contain three positive integers $a_i, b_i, c_i$ ($1 \le a_i \le b_i \le n$, $1 \le c_i \le 5\times 10^5$).

Output Format

On the first line, output a single positive integer — the maximum total spending.
On the second line, output $n$ positive integers, representing the prices $p_i$ of each shop from left to right, with $1 \le p_i \le 5\times 10^5$. If there are multiple optimal solutions, output any of them.

7 5
1 4 7
3 7 13
5 6 20
6 7 1
1 2 5

43
5 5 13 13 20 20 13

Hint

Original title: Myjnie.

Translated by ChatGPT 5