17695번 - Arranging Tickets 서브태스크다국어

In Republic of JOI, there are N stations numbered from 1 to N. They are located clockwise on a circular railway in order.

There are N types of train tickets numbered from 1 to N. By using one ticket of type i (1 ≤ i ≤ N − 1), one person can travel from the station i to the station i + 1, or from the station i + 1 to the station i. By using one ticket of type N, one person can travel from the station 1 to the station N, or from the station N to the station 1. We can only buy a package of N tickets consisting of one ticket for each type.

You are working at a travel agency in Republic of JOI. Your task is to arrange tickets for customers.

Today, you have M requests for arranging tickets. The i-th request says C_i people want to travel from the station A_i to the station B_i. These C_i people need not to take the same route when they travel.

You want to know the minimum number of packages of tickets you need to buy in order to deal with all the requests.

Given the number of stations and information of requests, write a program which calculates the minimum number of packages of tickets you need to buy.

Read the following data from the standard input.

• The first line of input contains two space separated integers N, M. This means there are N stations in Republic of JOI, and you have M requests today.
• The i-th line (1 ≤ i ≤ M) of the following M lines contains three space separated integers A_i, B_i, C_i. This means the i-th request says C_i people want to travel from the station A_i to the station B_i.

Write one line to the standard output. The output contains the minimum number of packages of tickets you need to buy.

• 3 ≤ N ≤ 200 000.
• 1 ≤ M ≤ 100 000.
• 1 ≤ A_i ≤ N (1 ≤ i ≤ M).
• 1 ≤ B_i ≤ N (1 ≤ i ≤ M).
• 1 ≤ C_i ≤ 1 000 000 000 (1 ≤ i ≤ M).
• A_i ≠ B_i (1 ≤ i ≤ M).

• N ≤ 20.
• M ≤ 20.
• C_i = 1 (1 ≤ i ≤ M).

• N ≤ 300.
• M ≤ 300.
• C_i = 1 (1 ≤ i ≤ M).

• N ≤ 3 000.
• M ≤ 3 000.
• C_i = 1 (1 ≤ i ≤ M).

• C_i = 1 (1 ≤ i ≤ M).

There are no additional constraints.