门票安排
题号：NC53204
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

题目译自 JOISC 2017 Day2 T1「切符の手配 / Arranging Tickets」
某条铁路环线共有N个车站，顺时针依次编号为。
该线路有N种车票，分别编号为。一张车票仅供一人从车站i顺时针移动到车站i+1，或供一人从车站i+1逆时针移动到车站i。一张车票N仅供一人从车站N顺时针移动到车站1，或供一人从车站1逆时针移动到车站N。
购买车票只有一种方法：购买套餐，套餐包含车票各1张。你是一名导游，你正在为游客订票。现有M个订票请求，订票请求表示从车站A_i到车站B_i有C_i名旅客（路线可以不同）。
求最少需要购买多少套餐。

输入描述:

第一行有两个整数N,M，用空格分隔。
在接下来的M行中，第i行有三个整数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给第三个人。
没有更优的方案。

备注:


CC-BY-SA，感谢LOJ分享，译文来自  https://loj.ac/problem/2393