4405: 「JOISC 2017 Day 2」门票安排
内存限制：256 MB
时间限制：4.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
**题目译自 [JOISC 2017](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/index.html) Day2 T1「[切符の手配](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d2.pdf) / [Arranging Tickets](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d2-en.pdf)」**
某条铁路环线共有 $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$，用空格分隔。
输出
一个整数，表示最少需要购买的套餐数。
样例输入 复制
3 3
1 2 1
2 3 1
3 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
数据范围：|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$|$C_i \leq 10^9$|