AT_joisc2017_d.切符の手配 (Arranging Tickets)

#「JOISC 2017 Day 2」门票安排

题目译自 JOISC 2017 Day2 T1「切符の手配（Arranging Tickets）」

某条铁路环线共有 $N$ 个车站，顺时针依次编号为 $1\ldots N$。
该线路有 $N$ 种车票，分别编号为 $1\ldots N$。一张车票 $i(1\le i\le N-1)$ 仅供一人从车站 $i$ 顺时针移动到车站 $i+1$，或供一人从车站 $i+1$ 逆时针移动到车站 $i$。一张车票 $N$ 仅供一人从车站 $N$ 顺时针移动到车站 $1$，或供一人从车站 $1$ 逆时针移动到车站 $N$。
购买车票只有一种方法：购买套餐，套餐包含车票 $1\ldots 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$，用空格分隔。

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

样例

样例输入 1

3 3
1 2 1
2 3 1
3 1 1

样例输出 1

1

样例解释 1

所有人都顺时针移动。

样例输入 2

3 2
1 2 4
1 2 2

样例输出 2

3

样例解释 2

下面是一种需购买 $3$ 个套餐的方法：

• 对于请求 $1$，$3$ 人顺时针移动，$1$ 人逆时针移动。
• 对于请求 $2$，$2$ 人逆时针移动。

没有更优的方案。

样例输入 3

6 3
1 4 1
2 5 1
3 6 1

样例输出 3

2

样例解释 3

把车票 $1,2,3$ 给第一个人，把车票 $1,6,5$ 给第二个人，把车票 $3,4,5$ 给第三个人。
没有更优的方案。

Subtask #	分值	$N$	$M$	$C_i(1\le i\le M)$
1	10	$N\le 20$	$M\le 20$	$C_i=1$
2	35	$N\le 300$	$M\le 300$	$C_i=1$
3	20	$N\le 3000$	$M\le 3000$	$C_i=1$
4	20	$N\le 2\times 10^5$	$M\le 10^5$	$C_i=1$
5	15	$N\le 2\times 10^5$	$M\le 10^5$

感谢 Planet6174 提供的翻译