티켓 배치

시간 제한4초메모리 제한256 MB

요약

원형 철도의 N개 역과 M개의 이동 요청이 주어졌을 때, 모든 요청을 처리하는 데 필요한 최소 승차권 묶음 수를 구합니다.

난이도: 어려움10점 중 9점
유형: 누적 합, 이분 탐색, 그리디
정답자: 아직 제출이 없습니다

문제

JOI 공화국에는 1번부터 $N$ 번까지 번호가 매겨진 $N$ 개의 역이 있다. 역들은 원형 철도를 따라 시계 방향으로 순서대로 놓여 있다.

티켓은 $N$ 종류이며 1번부터 $N$ 번까지 번호가 붙어 있다. 종류 $i$ ( $1 \le i \le N-1$ ) 티켓 한 장으로 한 사람이 역 $i$ 에서 역 $i+1$ 로, 또는 역 $i+1$ 에서 역 $i$ 로 이동할 수 있다. 종류 $N$ 티켓 한 장으로는 역 1에서 역 $N$ 으로, 또는 역 $N$ 에서 역 1로 이동할 수 있다. 티켓은 종류별로 한 장씩 담긴 $N$ 장 묶음 단위로만 구매할 수 있다.

여행사에서 일하며 손님들에게 티켓을 배정하는 것이 업무이다. 오늘 $M$ 건의 요청이 들어왔다. $i$ 번째 요청은 $C_i$ 명이 역 $A_i$ 에서 역 $B_i$ 로 이동하려 한다는 내용이다. 이 $C_i$ 명이 같은 경로로 이동할 필요는 없다.

모든 요청을 처리하기 위해 구매해야 하는 티켓 묶음의 최소 개수를 구하라.

입력

첫 줄에 역의 개수 $N$ 과 요청의 개수 $M$ 이 공백으로 구분된 정수로 주어진다.

이어지는 $M$ 개의 줄에는 공백으로 구분된 정수 $A_i$ , $B_i$ , $C_i$ 가 주어진다. 이는 $C_i$ 명이 역 $A_i$ 에서 역 $B_i$ 로 이동하려 한다는 뜻이다.

출력

모든 요청을 처리하는 데 필요한 티켓 묶음의 최소 개수를 한 줄에 출력한다.

제한

$3 \le N \le 200000$
$1 \le M \le 100000$
$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 1000000000$ ( $1 \le i \le M$ )
$A_i \ne B_i$ ( $1 \le i \le M$ )

예제3

예제 1
입력
```
3 3
1 2 1
2 3 1
3 1 1
```
예상 출력
```
1
```
예제 2
입력
```
3 2
1 2 4
1 2 2
```
예상 출력
```
3
```
예제 3
입력
```
6 3
1 4 1
2 5 1
3 6 1
```
예상 출력
```
2
```