超能侠喜欢坐火车，他常坐的一班车是一趟环线，共停靠n个站，其中n号站的下一个站是1号站。由于是环线，这趟火车也不存在起点站和终点站的说法。

一天，他坐火车时闲来无事，便观察起了上车的人群，并将其情况记录了下来。超能侠有超人的记忆力，所以能记住每个人上车和下车的车站。他一共记录了m条，每条记录（x,y,z）表示有z个人在x站上车，y站下车。

望着火车长长的车厢和上上下下的人群，超能侠突然想知道，按照记录中的情况，铁路部门至少需要多少节车厢才能让每个人都有座位呢？已知每节车厢有36个座位。

输入文件第一行给出两个整数n,m。

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

输出文件只有一行一个整数，表示至少需要多少节车厢。

对于40%的数据，2≤n≤1000，1≤m≤10000；

对于100%的数据，2≤n≤1000000，1≤m≤1000000，x≠y，1≤z≤100。