Description

In Xiao Z's hometown, there is a train running on a circular railway, stopping at $n$ stations (stations $1$ to $n$ arranged clockwise).

As everyone knows, the Spring Festival travel rush is a terrible thing. Unfortunately, Xiao Z is an employee of the railway company, and he has received $m$ booking requests for the early hours of Chinese New Year's Eve. Each request $(x, y, z)$ means there are $z$ people traveling clockwise from station $x$ to station $y$. At each stop at a station, all passengers who need to board at that station will get on, and all passengers who need to alight at that station will get off.

Since the starting station is not fixed, Xiao Z wants to know the minimum number of carriages that must be assigned to this train (each carriage can carry $36$ people) to complete the transportation, and he hopes you can help him.

Input Format

The first line contains two integers $n, m$.

The next $m$ lines each contain three integers $x, y, z$.

Output Format

The first line contains an integer, representing the minimum number of carriages required for this train.

3 2
1 2 36
2 3 36

1

4 2
1 2 36
4 3 36

2

Hint

Constraints

For $30 \%$ of the testdata, $n \le 1000$, $m \le 10000$;

For $100 \%$ of the testdata, $1 \le n, m \le 10^6$, $x \ne y$, $1 \le z \le 100$.

Translated by ChatGPT 5