题目描述

小 Z 的家乡有一列在环形铁轨上行驶的火车，共停靠 $n$ 个站（$1$ 号站到 $n$ 号站顺时针排列）。

众所周知，春运是一件非常可怕的事情。不幸的是，小 Z 是铁路公司的员工，现在他收到了 $m$ 条除夕凌晨的订票申请，每个申请 $(x, y, z)$ 表示有 $z$ 个人要从 $x$ 号站顺时针坐到 $y$ 号站，同时，当火车停靠到 $x$ 号站时，所有要在 $x$ 站上车的人都会上车，所有要在 $x$ 号站下车的人都会下车。

由于始发站不确定，现在小 Z 想知道至少需要分配给这列火车多少节车厢（每节车厢可容纳 $36$ 人）才能顺利完成该铁路运输，希望你帮帮他。

输入格式

第一行包含两个整数 $n, m$。

接下来 $m$ 行，每行包含三个整数 $x, y, z$。

输出格式

第一行包含一个整数，表示至少需要分配给这列火车的车厢数。

3 2
1 2 36
2 3 36

1

4 2
1 2 36
4 3 36

2

提示

【数据规模】

对于 $30 \%$ 的数据，$n \le 1000$，$m \le 10000$；

对于 $100 \%$ 的数据，$1 \le n, m \le 10^6$，$x \ne y$，$1 \le z \le 100$。