Description

给定一个 N 个点 M 条边的无向图，求无向图的严格次小生成树。设最小生成树的边权之和为sum，严格次小生成树的就是指边权之和大于sum中的生成树中最小的一个。

Format

Input

第一行包含两个整数N 和M，表示无向图的点数与边数。
接下来 M行，每行 3个数x y z 表示，点 x 和点y之间有一条边，边的权值为z。

Output

包含一行，仅一个数，表示严格次小生成树的边权和。(数据保证必定存在严格次小生成树)

Sample 1

Input

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

Output

11

Limitation

1s, 512MiB for each test case.

【数据规模】
数据中无向图无自环；
50% 的数据N≤2 000 M≤3 000；
80% 的数据N≤50 000 M≤100 000；
100% 的数据N≤100 000 M≤300 000 ，边权值非负且不超过 10^9 。

Source

BeiJing2010组队、bzoj1977