Optimal Pricing for Car Wash Shops

There are n car‐wash shops arranged in a row (indexed from 1 to n). You are to assign each shop a positive integer price p_i. There are also m customers. The i-th customer will drive past the shops from index a_i to b_i (inclusive) and will choose the shop with the lowest price among these. However, if the minimum price in that range is greater than c_i, then the customer will not get a car wash at all. The revenue collected from a customer is the minimum price in his/her interval (provided that it does not exceed c_i), otherwise the revenue is 0.

Your task is to assign a price to every shop such that the total revenue (i.e. the sum of the money spent by all customers) is maximized. If an interval contains one or more shops with finite prices, the revenue collected from that customer is the minimum price among those shops – but note that if this minimum is greater than the customer’s threshold c_i, the customer won’t buy the service and pays nothing.

Note on the optimal solution: In an optimal assignment the idea is to allow some shops to take a relatively low price to "cap" the cost in customer intervals with low thresholds, while other shops (which do not force any customer to pay above his/her threshold) can be set arbitrarily high (we use 10⁹ in our solutions). In other words, for each customer with parameters (a_i, b_i, c_i), if at least one shop in the interval [a_i, b_i] is set to a price ≤ c_i, then that customer will pay the minimum price in his/her interval; otherwise he/she pays 0. Since you have full control over the shop prices, you want for as many customers as possible that minimum to be as high as possible – but it cannot exceed c_i! It turns out that one optimal strategy is to choose a subset of shops (assigning them prices equal to some customer threshold) so that every customer’s interval includes at least one “dedicated” shop and then set all other shop prices to 10⁹.

inputFormat

The first line contains two integers n and m (the number of shops and the number of customers).

Then m lines follow. The i-th of these lines contains three positive integers: a_i, b_i, c_i (1 ≤ a_i ≤ b_i ≤ n) describing a customer’s interval and threshold.

You may assume that all numbers are small enough so that a brute‐force (backtracking) solution is feasible (for example, n ≤ 10 and m ≤ 10).

outputFormat

Output two lines. The first line should contain the maximum total revenue achievable. The second line should contain n positive integers, where the i-th integer is the assigned price p_i for shop i. If there are multiple optimal assignments, output any one of them. (Note: In our solutions, unassigned shops will be given the value 10⁹.)

sample

2 2
1 1 10
1 2 5

15
10 5