Grammy有一個簡單連通無向圖。每條邊都寫有一個數值。請幫佢揀一個簡單環，令到環上面寫嘅數值有最大嘅範圍。

一個環嘅範圍定義為環上面最大數值同最細數值嘅差。

一個環 $i_1 - e_1 - i_2 - e_2 - \cdots - i_k - e_k - i_1$（$e_j$ 係圖入面連接頂點 $i_j$ 同 $i_{j\bmod k+1}$ 嘅某條邊）係簡單嘅，若且唯若每條邊喺入面最多出現一次。

題目保證圖入面至少有一個環。

輸入

第一行有 $2$ 個整數 $n,m$（$3 \leq n \leq m \leq 10^5$），代表圖嘅頂點數目同邊數目。題目保證每對頂點之間最多有一條邊。

跟住 $m$ 行，每行有 $3$ 個整數 $u,v,w$（$1\leq u,v \leq n, -10^9\leq w \leq 10^9, u \neq v$），表示頂點 $u$ 同頂點 $v$ 之間有一條邊，上面寫住數值 $w$。

輸出

輸出一個整數佔一行，代表圖入面簡單環嘅最大可能範圍。

例子

輸入 1

5 7
1 2 1
1 3 -2
2 3 1
3 4 3
4 5 1
1 5 -1
2 5 2

輸出 1

5

備註

喺第一個樣本入面，環 1-2-5-4-3-1 有最大範圍 $5$，因為環上面最大數值係 $3$，最細數值係 $-2$，所以範圍係 $3-(-2)=5$。可以證明冇任何環嘅範圍大過 $5$。