MathJax.Hub.Config({
  tex2jax: {
    inlineMath: [["$","$"], ["\\(","\\)"]],
    processEscapes: true
  }
});

题目描述

Awesome Conveyor Machine (ACM) 是 Industrial Conveyor Product Corporation (ICPC) 工厂中最重要的设备。ACM 有一条长长的传送带，用于将产品从一个点运送到另一个点。你是一名被雇佣的程序员，负责制定高效的产品交付计划。

ACM 的传送带经过 $N$ 个等距离的点。每个点上都可以放置最多一个产品。初始时，所有点上都没有产品。传送带每秒移动一个板的长度；经过一秒钟，一块板在位置1，其他位置都没有板。再过一秒钟，位置1的板移到位置2，位置1有一个新的板，以此类推。传送带上的板的数量是无限的：在经过 $N$ 秒或更长时间后，每个位置上都恰好有一块板。

一个交付任务由起点 $a$ 和终点 $b$ 表示；在传送带上放置一个产品在位置 $a$，$b-a$ 秒后从位置 $b$ 取回产品（$a<b$）。（当然，在放置时必须存在一个空板在放置位置上。）此外，放置和取回产品必须按照以下规则进行：

• 放置和取回产品时，板必须正好位于相应的位置。也就是说，产品必须在整数秒放置和取回。
• 同一位置上不能同时放置和取回产品。然而，在不同的位置上可以同时进行放置和取回。

如果存在多个任务，通过在每个产品放置在传送带上时改变计划，可以缩短完成所有任务的时间。你的任务是编写一个程序，以尽量减少完成所有任务的时间...等等。你是从何时开始误解了初始就知道所有任务的想法的？新的交付请求如同传送带上的板一样源源不断！因此，你应该根据每个新的请求更新最优的计划。

一个请求包含起点 $a$，终点 $b$ 和要交付的产品数量 $p$。将会有 $Q$ 个交付请求。你的真正任务是编写一个程序，对于每个 $1 \le i \le Q$，求解从请求1到请求 $i$ 所有交付任务所需的总时间的最小值。

---

输入

输入由一组格式如下的测试用例组成。

$N$ $Q$ $a_1$ $b_1$ $p_1$ $\vdots$ $a_Q$ $b_Q$ $p_Q$

第一行包括两个整数 $N$ 和 $Q$ ($2 \le N \le 10^5$, $1 \le Q \le 10^5$)：$N$ 是传送带经过的位置数量，$Q$ 是即将到来的请求数量。接下来的 $Q$ 行中的第 $i$ 行包含三个整数 $a_i$, $b_i$ 和 $p_i$ ($1 \le a_i < b_i \le N$, $1 \le p_i \le 10^9$)，表示第 $i$ 个请求需要将 $p_i$ 个产品从位置 $a_i$ 送到位置 $b_i$。

输出

在第 $i$ 行中，输出从请求1到请求 $i$ 所有交付任务所需的最短时间。

---

示例输入 1

5 2
1 4 1
2 3 1

示例输出 1

4
4

---

示例输入 2

5 2
1 4 1
2 3 5

示例输出 2

4
8

---

示例输入 3

5 2
1 3 3
3 5 1

示例输出 3

5
6

---

示例输入 4

10 4
3 5 2
5 7 5
8 9 2
1 7 5

示例输出 4

6
11
11
16

---

注意

对于第一个示例，只完成第一个请求所需的最短时间是 $4$ 秒。两个请求都可以在 $4$ 秒内完成。以下是示例图：

---