在 JOI 共和国，有 $N$ 个车站，编号从 $1$ 到 $N$。它们按顺时针方向排列在一个环形铁路上。

共有 $N$ 种火车票，编号从 $1$ 到 $N$。使用一张 $i$ 型车票（$1 \le i \le N - 1$），乘客可以从车站 $i$ 前往车站 $i+1$，或者从车站 $i+1$ 前往车站 $i$。使用一张 $N$ 型车票，乘客可以从车站 $1$ 前往车站 $N$，或者从车站 $N$ 前往车站 $1$。我们只能购买包含每种车票各一张的“车票包”。

你在 JOI 共和国的一家旅行社工作，你的任务是为客户安排车票。 今天，你收到了 $M$ 个购票请求。第 $i$ 个请求表示有 $C_i$ 个人想要从车站 $A_i$ 前往车站 $B_i$。这 $C_i$ 个人在旅行时不需要走相同的路线。

你需要计算为了满足所有请求，最少需要购买多少个车票包。

输入格式

从标准输入读取以下数据：

• 第一行包含两个空格分隔的整数 $N, M$。这表示 JOI 共和国有 $N$ 个车站，你今天有 $M$ 个请求。
• 接下来的 $M$ 行中，第 $i$ 行（$1 \le i \le M$）包含三个空格分隔的整数 $A_i, B_i, C_i$。这表示第 $i$ 个请求有 $C_i$ 个人想要从车站 $A_i$ 前往车站 $B_i$。

输出格式

输出一行到标准输出，包含最少需要购买的车票包数量。

数据范围

所有输入数据满足以下条件：

• $3 \le N \le 200\,000$
• $1 \le M \le 100\,000$
• $1 \le A_i \le N$ ($1 \le i \le M$)
• $1 \le B_i \le N$ ($1 \le i \le M$)
• $1 \le C_i \le 1\,000\,000\,000$ ($1 \le i \le M$)
• $A_i \neq B_i$ ($1 \le i \le M$)

子任务

共有 5 个子任务，各子任务的分值及附加限制如下：

• 子任务 1 [10 分]：$N \le 20$，$M \le 20$，$C_i = 1$ ($1 \le i \le M$)。
• 子任务 2 [35 分]：$N \le 300$，$M \le 300$，$C_i = 1$ ($1 \le i \le M$)。
• 子任务 3 [20 分]：$N \le 3\,000$，$M \le 3\,000$，$C_i = 1$ ($1 \le i \le M$)。
• 子任务 4 [20 分]：$C_i = 1$ ($1 \le i \le M$)。
• 子任务 5 [15 分]：无附加限制。

样例

样例输入 1

3 3
1 2 1
2 3 1
3 1 1

样例输出 1

1

样例输入 2

3 2
1 2 4
1 2 2

样例输出 2

3

样例输入 3

6 3
1 4 1
2 5 1
3 6 1

样例输出 3

2