[AdditionalFile2393.zip](file://AdditionalFile2393.zip?type=additional_file)

#2393. 「JOISC 2017 Day 2」门票安排

标签: 传统 | 时间限制: 4000 ms | 内存限制: 256 MiB |

题目描述

题目译自 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

所有人都顺时针移动。

样例 2

输入

3 2
1 2 4
1 2 2

输出

3

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

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

没有更优的方案。

样例 3

输入

6 3
1 4 1
2 5 1
3 6 1

输出

2

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

数据范围与提示