Arranging Tickets

Time limit4sMemory limit256 MB

Summary

Given N stations on a circular railway and M travel requests with passenger counts, find the minimum number of ticket packages needed to serve all requests.

Level: Hard9 of 10
Topics: Prefix sum, Binary search, Greedy
Solved: No attempts yet

Problem

Republic of JOI has $N$ stations numbered from 1 to $N$ . They are placed in order along a circular railway, clockwise.

There are $N$ types of train tickets, numbered from 1 to $N$ . One ticket of type $i$ ( $1 \le i \le N-1$ ) lets one person travel from station $i$ to station $i+1$ , or from station $i+1$ to station $i$ . One ticket of type $N$ lets one person travel from station 1 to station $N$ , or from station $N$ to station 1. Tickets can only be bought as a package of $N$ tickets, with one ticket of each type.

You work at a travel agency in Republic of JOI, and your job is to arrange tickets for customers. Today you have $M$ requests. The $i$ -th request says that $C_i$ people want to travel from station $A_i$ to station $B_i$ . These $C_i$ people do not need to take the same route.

Find the minimum number of ticket packages you need to buy to handle all requests.

Input

The first line contains two space-separated integers $N$ and $M$ , the number of stations and the number of requests.

Each of the next $M$ lines contains three space-separated integers $A_i$ , $B_i$ , and $C_i$ . This means $C_i$ people want to travel from station $A_i$ to station $B_i$ .

Output

Print one line containing the minimum number of ticket packages needed to handle all requests.

Constraints

$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$ )

Examples3

Example 1
Input
```
3 3
1 2 1
2 3 1
3 1 1
```
Expected output
```
1
```
Example 2
Input
```
3 2
1 2 4
1 2 2
```
Expected output
```
3
```
Example 3
Input
```
6 3
1 4 1
2 5 1
3 6 1
```
Expected output
```
2
```