Byteasar 计划参与一项在 Byteotia 的主要高速公路沿线经营 $n$ 个洗车店的投标。在投标之前，他希望估算自己能获得的收入。

为此，他委托进行了一项市场调研。调研结果显示，将有 $m$ 位潜在客户沿该公路行驶。具体来说，第 $i$ 位客户将沿 $a_i$ 到 $b_i$ 之间的路段（包含端点）行驶，如果洗车价格不超过 $c_i$ bythalers，他们就有兴趣洗车。Byteasar 打算独立设定每家洗车店的价格。假设每位客户都是理性的（且爱干净的！）代理人，即他们会选择沿途最便宜的洗车店，如果所有洗车店的价格都超过了他们的预算，则选择不洗车。Byteasar 希望通过设定价格来最大化他的总收入。

输入格式

标准输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 50, 1 \le m \le 4000$)，用空格分隔，分别表示洗车店的数量和客户的数量。洗车店编号为 $1$ 到 $n$。接下来的 $m$ 行描述了客户信息：第 $i$ 行包含三个整数 $a_i, b_i$ 和 $c_i$ ($1 \le a_i \le b_i \le n, 1 \le c_i \le 500\,000$)，用空格分隔，表示第 $i$ 位客户沿 $a_i$ 到 $b_i$ 的路段行驶，且洗车预算为 $c_i$ bythalers。

在总分占比 75% 的测试点中，满足额外条件 $m \le 250$。

输出格式

第一行应包含一个整数 $s$，等于 Byteasar 的最大总收入（以 bythalers 为单位）。第二行应包含实现该收入 $s$ 的价格列表（在理性代理人假设下），即一个包含 $n$ 个整数的序列 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le 500\,000$)，用空格分隔，其中 $p_i$ 是第 $i$ 家洗车店的价格。如果存在多个正确答案，程序可以任意输出其中一个。

样例

输入 1

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

输出 1

43
5 5 13 13 20 20 13

说明

如果第一行输出不正确，该测试点将不得分。如果第一行输出正确但其余部分不正确，将获得该测试点 60% 的分数。即使答案不符合输出格式（例如打印了一行以上或价格列表格式错误），此规则依然有效。

样例评分测试：

• 1ocen: $n = 5, m = 2$；第一位客户经过所有洗车店且预算为 10，第二位客户仅经过第三家洗车店且预算为 9；在最优解中，第三家洗车店的价格应为 9 bythalers，其他所有洗车店的价格应高于 9 —— 在这种情况下，两位客户各支付 9 bythalers 洗车，Byteasar 获得收入 $2 \cdot 9 = 18$；
• 2ocen: $n = 2, m = 8$；三位客户预算为 3，经过所有洗车店；三位客户预算为 1，仅经过第一家洗车店；两位客户预算为 1，仅经过第二家洗车店；在最优解中，每家洗车店的价格应为 3 bythalers —— 在这种情况下，只有前三位客户各支付 3 bythalers 洗车，Byteasar 获得收入 $3 \cdot 3 = 9$；
• 3ocen: $n = 50, m = 1000$；第 $i$ 位客户经过所有洗车店且预算为 $500 \cdot i$；在最优解中，每家洗车店的价格应为 250 000 bythalers —— 在这种情况下，只有编号 500 到 1000 的客户会洗车，Byteasar 获得收入 $501 \cdot 250\,000 = 125\,250\,000$。