oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

newtown Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

construction.html

Problem Description

Peanut is the mayor of a new city, Silvermill. Silvermill has N towns, numbered 0 to N-1, which are completely disconnected from one another. He hires a contractor, who gives him a list of E proposed roads, with the ith road proposed to connect towns Ai and Bi directly, at the cost of Ci dollars.

Peanut wishes to build a subset of roads proposed by the contractor, such that between any two towns, there exists a direct or indirect path between them. Help Peanut find the minimum possible cost of achieving this. It is guaranteed that there exists at least one subset of chosen roads that would accomplish this goal.

Input

The first line of input will contain two integers, N and E.

The next E lines of input will contain three integers each, Ai, Bi and Ci.

Output

The output should contain exactly one integer, the minimum cost, in terms of dollars, that Peanut needs to spend to connect the towns of Silvermill to one another.

Limits

1 ≤ N, E ≤ 106.

0 ≤ Ai, Bi < N.

1 ≤ Ci ≤ 109.

Sample Input

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

Sample Output

3

Tags

Graph Theory, Minimum Spanning Tree, Classic

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100312s256MBMinimum
2012s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o newtown -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.