시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 256 MB2510834.783%

문제

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 Ci people want to travel from the station Ai to the station Bi. These Ci 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 Ai, Bi, Ci. This means the i-th request says Ci people want to travel from the station Ai to the station Bi.

출력

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 ≤ Ai ≤ N (1 ≤ i ≤ M).
• 1 ≤ Bi ≤ N (1 ≤ i ≤ M).
• 1 ≤ Ci ≤ 1 000 000 000 (1 ≤ i ≤ M).
• Ai ≠ Bi (1 ≤ i ≤ M).

서브태스크 1 (10점)

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

서브태스크 2 (35점)

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

서브태스크 3 (20점)

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

서브태스크 4 (20점)

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

예제 입력 1

3 3
1 2 1
2 3 1
3 1 1


예제 출력 1

1


If everybody travels clockwise, you need one ticket for each type. Hence you need to buy one package of tickets.

예제 입력 2

3 2
1 2 4
1 2 2


예제 출력 2

3


You need three tickets for each type if people travel in the following way:

• In the first request, three people travel clockwise, and one person travels counterclockwise.
• In the second request, two people travel counterclockwise.

Hence it is enough to buy three packages of tickets.

We output 3 because it is impossible to travel if you buy only two packages.

예제 입력 3

6 3
1 4 1
2 5 1
3 6 1


예제 출력 3

2


For example, you buy two packages of tickets, and distribute them in the following way:

• Give tickets 1, 2, 3 to the person who wants to travel from the station 1 to the station 4.
• Give tickets 1, 6, 5 to the person who wants to travel from the station 2 to the station 5.
• Give tickets 3, 4, 5 to the person who wants to travel from the station 3 to the station 6.

We output 2 because it is impossible to travel if you buy one package only.

채점 및 기타 정보

• 예제는 채점하지 않는다.