题目描述

在 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 3
1 2 1
2 3 1
3 1 1

1

3 2
1 2 4
1 2 2

3

6 3
1 4 1
2 5 1
3 6 1

2

提示

样例 1 解释

若所有人都顺时针旅行，则每种票各需一张，因此你只需购买一个票包。

样例 2 解释

若人们按以下方式旅行，则每种票各需三张：

• 在第一个请求中，三人顺时针旅行，一人逆时针旅行。
• 在第二个请求中，两人逆时针旅行。

因此，购买三个票包已足够。我们输出 3，因为若仅购买两个票包，则无法完成所有旅行。

样例 3 解释

例如，你购买了两个票包，并按以下方式分配：

• 将票 1、2、3 给希望从车站 1 前往车站 4 的人。
• 将票 1、6、5 给希望从车站 2 前往车站 5 的人。
• 将票 3、4、5 给希望从车站 3 前往车站 6 的人。

我们输出 2，因为若仅购买一个票包，则无法完成所有旅行。

约束条件

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

• $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 \ne 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 分]

无额外约束。

翻译由 Qwen3-235B 完成