这题真的很难的

Morning_X今天又又又自闭了，因为被多校数学题+OEIS题锤爆了狗头

他今天又被Home_W抓住学数学题了，这道题目是这样子的

Home_W对一个可重实数集下了这样子一个定义{a_i}的离差为：对于任何实数∑_i|a_i-u|的最小值记为d({a_i})

例如数集{1,2,4}，的离差为3，因为当u=2时，∑_i∣a_i−μ∣=∣1−2∣+∣2−2∣+∣4−2∣=3 最小。

现在Home_W跟我说一颗携带边权的树，我们定义他的离差是所有边的边权组成的可重集合的离差

现在家旺又给了一张无向联通图，每条边都有边权，牛逼轰轰的Home_W让我求出它的最大离差生成树，就是所有生成树里面离差最大的那个，但是菜鸡的我怎么可能求的出来，于是为了避免我被锤爆狗头，我就把问题扔给了你们

第一行输入两个正整数n,m（2<=n<=2e5,1<=m<=5e5）代表一张图的点数和边数

接下来m行，每行三个整数,u,v,w，(1<=w<=1e9)用空格隔开

表示u,v之间有一条权值为w的无向边。点的编号从1~n

输出一个整数，代表最大的离差

4 6
1 2 1
1 3 2
2 3 5
3 2 4
2 4 3
3 4 2

4

7 8
1 2 91
2 3 63
1 4 77
2 5 10
3 6 56
6 7 89
6 2 40
6 7 89

151