题目描述

给出一个 $n$ 个点的无向稠密图，用 $m$ 条带权边描述（可能存在重边与自环）。请你求出这张图的最小生成树的边权之和。

若图不连通，则不存在生成树。

本题的顶点数较少而边数很多（两组数据满足 $m\ge n^2/4$），请选择合适的算法。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示连接 $u,v$ 的长度为 $w$ 的无向边。

输出格式

输出一行一个整数表示最小生成树的边权和。若图不连通，输出 orz。

输入输出样例 #1

输入 #1

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

输出 #1

12

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 1000$，$0\le m\le 3\times 10^5$，$1\le u,v\le n$，$1\le w\le 10^4$。边权和不超过 $10^7$。