Problem A: Construction (Easy-10) ## Problem A: Construction (Easy-10)

Time Limit: 1 Sec Memory Limit: 128 MB

Submit: 558 Solved: 201

[Submit][Status][Web Board]## Description

Yuki is a meticulous girl and she rules a country named Blossom.

Blossom is a big country with \(n\) cities, and there are \(m\) roads determined to be constructed. Due to many reasons during construction, different roads might have different costs to be built. The roads are **bidirectional**, that is a road from \(u\) to \(v\) **can** be passed from \(v\) to \(u\).

Since Yuki wants to make the construction more economical, she decides to choose some of the roads to construct and wants to spend the least money. However, to make the traffic in Blossom convenient, all the cities in Blossom are needed to be connected after construction. Your task is to determine the **minimum** cost of construction.

## Input

The first line contains two integers: \(n\) and \(m\) \((1 \leq n \leq 1\ 000,\ 1 \leq m \leq 10\ 000)\) — the number of cities and roads to be constructed in Blossom.

Each of the next \(m\) lines contains three space-separated integers: \(u\), \(v\) and \(w \) \((1 \leq u,\ v\leq n, \ 1 \leq w \leq 10^6)\), meaning that there is a bidirectional road from city \(u\) to city \(v\) considered to be built. And the cost of this edge is \(w\).

Cities are numbered from \(1\) to \(n\). It is guaranteed that there is at least one plan to connect all cities.

## Output

Print one line with an integer — the minimum cost of the construction.

## Sample Input

4 4
1 2 2
2 3 2
3 4 2
4 1 2

## Sample Output

6

## HINT

[Submit][Status]