P3592 [POI 2015 R3] Car Washes

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.

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$).

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.

Original title: Myjnie. Translated by ChatGPT 5