时间限制：1秒　　内存限制：256M

---

【问题描述】

　　偏远地区有 \(N\) 个村庄（按 \(1..N\) 顺次编号），政府打算修建一些公路把这 \(N\) 个地区连通。地质勘测队列举出可直接修建公路的村庄对，共有 \(M\) 对，其余那些由于地质原因无法修建。其中第i对的两个村庄分别为 \(a_i,b_i\)，在这两个村庄之间建立一条公路的造价为 \(c_i\)。作为工程师的你接受到政府的任务，请你规划要建造那些道路才能使 \(N\) 个村庄可以相互连通且造价最低。

　　在正在你规划时，政府突然接到国家安全部门的通知，说其中有一条公路存在军事风险而无法修建，但为保密，没有说究竟是那一条道路。只有在你的规划方案出来之后安全部门再予以审查。于是政府要求规划一个最坏情况的方案，即无论那一条道路无法修建，都会找到一个造价不超过你规划的造价的方案，请你给出你方案的最小代价。

【输入格式】

　　输入的第一行包含两个整数 \(N\) 和 \(M\)，表示村庄数目和能修建公路的村庄对数。接下来 \(M\) 行，每行三个数 \(a_i,b_i\) 和 \(c_i\) 表示村庄 \(a_i\) 和 \(b_i\) 之间可以修建一条道路，造价为 \(c_i\)。　

【输出格式】

　　输出一个整数，表示你规划方案的最小造价。

【输入输出样例】

　Input

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

　Output

12

【数据限制】

　　数据中无向图无自环；
　　50% 的数据 \(N≤2000，M≤3000\)；
　　80% 的数据 \(N≤50000， M≤100000\)；
　　100% 的数据 \(N≤100000， M≤300000 ，0<ci≤10^9\)。

【来源】

　　Mr.he