航空公司

题目描述:

     温州市龙湾国际机场要联通更多的航线，包括该机场在内有  \( n \) 个机场，m条航线，因不同机场距离不同，所以不同航线航行的价格有多有少，在第  \( i \) 条航线航行需要  \( c_i \) 万 RMB。

     机场经理要求从温州市龙湾国际机场能联通所有机场（可以间接联通，并假设温州市龙湾国际机场编号为  \( 1 \) ），现在他想知道最少需要几万RMB才能联通所有机场。

输入格式:

      第一行两个数，  \( n \) ，  \( m \) 表示  \( n \) 个机场  \( m \) 条航线。

      第二行到  \( m+1 \) 行，每行三个整数  \( x, y, c_i \) 表示从机场  \( x \) 到机场  \( y \) 有一条航行代价为  \( c_i \) 的航线（航线都是双向的）。

输出格式:

       一个数，表示最小代价。

样例输入:

5 7
1 2 4
1 4 9
1 5 6
2 3 10
2 4 7
3 4 8
4 5 20

样例输出:

25

提示:

对于60%的数据：n<=500,m<=700；

对于100%的数据：n<=7000,m<=10000,ΣCi<=1000000,数据保证图连通；

样例解释：

时间限制: 1000ms
空间限制: 256MB

---

来源: by zhr