Processing math: 100%
Minimum spanning tree - MarisaOJ: Marisa Online Judge

Minimum spanning tree

Time limit: 1000 ms
Memory limit: 256 MB

Given a connected, weighted, undirected graph of $n$ vertices and $m$ edges. Find weight of its minimum spanning tree.

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Input

  • The first line contain 2 integers $n, m$.
  • The next $m$ lines, each line contains 3 integers $u, v, w$, there is an edge weigh $w$ between $u$ and $v$.

Output

  • Print the weight of the minimum spanning tree.

Constraints

  • $1 \le n, m\le 10^5$.
  • $1 \le u, v \le n$.
  • $1 \le w \le 10^9$.

Example

Input:

3 3
1 2 1
2 3 2
3 1 3

Output:

3