题目描述

小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 ≤ 1000，m ≤ 10000；

对于 100% 的数据，1 ≤ n，m ≤ 10^6，x ≠ y，1 ≤ z ≤ 100。