小Z的车厢
题目描述
小 Z 的家乡有一列在环形铁轨上行驶的火车,共停靠 $n$ 个站($1$ 号站到 $n$ 号站顺时针排列)。
众所周知,春运是一件非常可怕的事情。不幸的是,小 Z 是铁路公司的员工,现在他收到了 $m$ 条除夕凌晨的订票申请,每个申请 $(x, y, z)$ 表示有 $z$ 个人要从 $x$ 号站顺时针坐到 $y$ 号站,同时,当火车停靠到 $x$ 号站时,所有要在 $x$ 站上车的人都会上车,所有要在 $x$ 号站下车的人都会下车。
由于始发站不确定,现在小 Z 想知道至少需要分配给这列火车多少节车厢(每节车厢可容纳 $36$ 人)才能顺利完成该铁路运输,希望你帮帮他。
输入输出格式
输入格式
第一行包含两个整数 $n, m$。
接下来 $m$ 行,每行包含三个整数 $x, y, z$。
输出格式
第一行包含一个整数,表示至少需要分配给这列火车的车厢数。
输入输出样例
输入样例 #1
3 2
1 2 36
2 3 36
输出样例 #1
1
输入样例 #2
4 2
1 2 36
4 3 36
输出样例 #2
2
说明
**【数据规模】**
对于 $30 \%$ 的数据,$n \le 1000$,$m \le 10000$;
对于 $100 \%$ 的数据,$1 \le n, m \le 10^6$,$x \ne y$,$1 \le z \le 100$。