Problem Description

Little Z's hometown has a train that runs on a circular track, stopping at \( n \) stations (numbered \( 1 \) to \( n \) in a clockwise order).

It is well known that the Spring Festival travel rush is a terrifying event. Unfortunately, Little Z works for the railway company, and now he has received \( m \) ticket booking requests for the early hours of New Year's Eve. Each request \( (x, y, z) \) indicates that \( z \) people want to travel clockwise from station \( x \) to station \( y \). Additionally, when the train stops at station \( x \), all people who need to board at station \( x \) will board, and all people who need to alight at station \( x \) will alight.

Since the starting station is uncertain, Little Z wants to know the minimum number of train carriages (each carriage can accommodate \( 36 \) people) that need to be allocated to this train to successfully complete the railway transportation. He hopes you can help him.

Input Format

The first line contains two integers \( n \) and \( m \).

The next \( m \) lines each contain three integers \( x \), \( y \), and \( z \).

Output Format

The first line contains a single integer, representing the minimum number of train carriages needed.

Sample Input and Output

Sample Input #1

3 2
1 2 36
2 3 36

Sample Output #1

1

Sample Input #2

4 2
1 2 36
4 3 36

Sample Output #2

2

Notes

[Data Range]

For \( 30\% \) of the data, \( n \le 1000 \), \( m \le 10000 \);

For \( 100\% \) of the data, \( 1 \le n, m \le 10^6 \), \( x \ne y \), \( 1 \le z \le 100 \).

见题面 Input 部分

见题面 Output 部分