俊吉主任(簡稱鈞任)是一位熱愛海洋的8+9，家裡擁有許多的小島，而且從小時候就非常喜愛魔法城堡，而長大成人的他現在是一位土木工程師。
他想要著手建造他所夢想的魔法城堡。但是由於經費不足，鈞任想出一套解決辦法：
在海洋上規劃一個旅行，船從小島1出發，依序經過小島2, 3, ... n-1，最後到達小島n，在每個小島，民眾可以選擇在此小島上船或是下船。
後來他發現他的客戶跟「日本進口壓縮機」一樣稀少，所以他打算統計從小島i到j途中船上人數的最大值\((1 <= i, j <= n, i < j)\)，以便調整方案。

Input

輸入僅包含一筆測資。
第一列有1個正整數\(n\)代表小島數量。
第二列有一個正整數\(m\)，代表有m筆乘客資訊。
接下來有\(m\)列，每列包含\(i, j, k(1 <= i, j <= n, i < j)\)，代表\(k\)個乘客有相同行為，都是從小島\(i\)上船，小島\(j\)下船。

Output

請輸出人數的最大值為多少
PS: 假如乘客在j島下船，則在統計人數時視為還在船上；若有乘客上船，則統計人數時會計算到上船的旅客。

Constraints

第 \(1\) 組測資, \(n\leq10^3\), \(m\leq10\)。 \((20\text{%})\)

第 \(2\) 組測資, \(n\leq10^4\), \(i+1=j\)。 \((20\text{%})\)

第 \(3\) 組測資, \(n\leq2*10^5\)。\((20\text{%})\)

第 \(4\) 組測資, \(n\leq2^{50}\)。\((40\text{%})\)

對於所有測資，\(m<=10^5\), \(k<=1000\)。

Sample Input

6
3
2 5 2
3 6 5
1 4 10

Sample Output

17