4380 - [POI2015]Myjnie

有n家洗车店从左往右排成一排，每家店都有一个正整数价格p[i]。 有m个人要来消费，第i个人会驶过第a[i]个开始一直到第b[i]个洗车店，且会选择这些店中最便宜的一个进行一次消费。但是如果这个最便宜的价格大于c[i]，那么这个人就不洗车了。 请给每家店指定一个价格，使得所有人花的钱的总和最大。

第一行包含两个正整数n,m(1<=n<=50，1<=m<=4000)。 接下来m行，每行包含三个正整数a[i],b[i],ci

第一行输出一个正整数，即消费总额的最大值。 第二行输出n个正整数，依次表示每家洗车店的价格p[i]，要求1<=p[i]<=500000。 若有多组最优解，输出任意一组。