P14385 [JOISC 2017] 门票安排 / Arranging Tickets

在 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$。

向标准输出写入一行。该行输出包含你最少需要购买的票包数量。

### 样例 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 完成