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

powergrid Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

powergrid.html

Problem Description

Damian is now managing the power grid for his district of N towns numbered 1 to N. There are M power lines in his power grid numbered 1 to M. Each power line connects two towns, the ith power line connects town Ai and Bi, and costs Ci

FanPu has just taken presidency of the district and has ordered Damian to cut down on the number of power lines in order to Make District Great Again. He wants Damian to remove power lines in some way such that only N - 1 power lines remain, and that all towns must still be connected to one another directly or indirectly via power lines after the removal.

Damian now wants to know, for the ith power line, what is the minimum possible total cost of the remaining power lines if he keeps the ith power line as part of the remaining power lines in the power grid.

Damian wants to know the above for each of the M power lines. Please help him.

Input

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

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

Output

The ith line should contain one integer, the minimum possible total cost of the remaining power lines if the ith power line is part of the remaining power lines.

Limits

For all subtasks, 1 ≤ Ai, Bi ≤ N. 1 ≤ Ci ≤ 109.

Subtask 1 (37%): 2 ≤ N ≤ 500. N - 1 ≤ M ≤ 1000.

Subtask 2 (63%): 2 ≤ N ≤ 200 000. N - 1 ≤ M ≤ 400 000.

Subtask 3 (0%): Sample Testcases

Sample Testcase 1

Input

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

Output

9
8
11
8
8
8
9

Tags

Graph Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
137301s256MBMinimum
263401s256MBMinimum
3011s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o powergrid -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.