某条铁路环线共有 $N$ 个车站，顺时针依次编号为 $1\dots N$。

该线路有 $N$ 种车票，分别编号为 $1\dots N$。一张车票 $i(1\le i\le N-1)$ 仅供一人从车站 $i$ 顺时针移动到车站 $i+1$，或供一人从车站 $i+1$ 逆时针移动到车站 $i$。一张车票 $N$ 仅供一人从车站 $N$ 顺时针移动到车站 $1$，或供一人从车站 $1$ 逆时针移动到车站 $N$。

购买车票只有一种方法：购买套餐，套餐包含车票 $1\dots N$ 各 $1$ 张。

你是一名导游，你正在为游客订票。现有 $M$ 个订票请求，订票请求 $i(1\le i\le M)$ 表示从车站 $A_i$ 到车站 $B_i$ 有 $C_i$ 名旅客（路线可以不同）。

求最少需要购买多少套餐。

输入格式

第一行有两个整数 $N,M$，用空格分隔。

在接下来的 $M$ 行中，第 $i$ 行 $(1\le i\le M)$ 有三个整数 $A_i,B_i,C_i$，用空格分隔。

输出格式

一个整数，表示最少需要购买的套餐数。

样例一

input

3 3
1 2 1
2 3 1
3 1 1

output

1

explanation

所有人都顺时针移动。

样例二

input

3 2
1 2 4
1 2 2

output

3

explanation

下面是一种需购买 $3$ 个套餐的方法： - 对于请求 $1$，$3$ 人顺时针移动，$1$ 人逆时针移动。 - 对于请求 $2$，$2$ 人逆时针移动。

没有更优的方案。

样例三

input

6 3
1 4 1
2 5 1
3 6 1

output

2

explanation

把车票 $1,2,3$ 给第一个人，把车票 $1,6,5$ 给第二个人，把车票 $3,4,5$ 给第三个人。

没有更优的方案。

数据范围与提示

对于所有数据，保证 $3\le N\le 2\times {10}^5,1\le M\le {10}^5,1\le A_i,B_i\le N,1\le C_i\le {10}^9,A_i\ne B_i$。

时间限制：$4\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$