UOJ Logo Universal Online Judge

UOJ

#358. 【JOISC2017】Arranging Tickets

附件下载 统计

某条铁路环线共有 N 个车站,顺时针依次编号为 1N

该线路有 N 种车票,分别编号为 1N。一张车票 i(1iN1) 仅供一人从车站 i 顺时针移动到车站 i+1,或供一人从车站 i+1 逆时针移动到车站 i。一张车票 N 仅供一人从车站 N 顺时针移动到车站 1,或供一人从车站 1 逆时针移动到车站 N

购买车票只有一种方法:购买套餐,套餐包含车票 1N1 张。

你是一名导游,你正在为游客订票。现有 M 个订票请求,订票请求 i(1iM) 表示从车站 Ai 到车站 BiCi 名旅客(路线可以不同)。

求最少需要购买多少套餐。

输入格式

第一行有两个整数 N,M,用空格分隔。

在接下来的 M 行中,第 i(1iM) 有三个整数 Ai,Bi,Ci,用空格分隔。

输出格式

一个整数,表示最少需要购买的套餐数。

样例一

input

3 3
1 2 1
2 3 1
3 1 1

output

1

explanation

所有人都顺时针移动。

样例二

input

3 2
1 2 4
1 2 2

output

3

explanation

下面是一种需购买 3 个套餐的方法: - 对于请求 13 人顺时针移动,1 人逆时针移动。 - 对于请求 22 人逆时针移动。

没有更优的方案。

样例三

input

6 3
1 4 1
2 5 1
3 6 1

output

2

explanation

把车票 1,2,3 给第一个人,把车票 1,6,5 给第二个人,把车票 3,4,5 给第三个人。

没有更优的方案。

数据范围与提示

子任务 分值 N M Ci(1iM)
1 10 N20 M20 Ci=1
2 35 N300 M300 Ci=1
3 20 N3000 M3000 Ci=1
4 20 N2×105 M105 Ci=1
5 15 N2×105 M105 Ci109

对于所有数据,保证 3N2×105,1M105,1Ai,BiN,1Ci109,AiBi

时间限制:4s

空间限制:256MB