Informatica Online Judge

  고용 [2140 / 085C]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 5   Total Tried : 6


The Champion of this Problem (C++) : gs16106 - 191ms / 1540byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]
Writer ID : [gs16022]

Background

승한이는 승한 나라의 대통령이다.

승한 나라에는 N개의 회사가 있고, 승한이는 승한 나라의 경제 발전을 위해 이 회사들을 하나로 합치려고 한다. 각 회사를 합치기 위해서는 두 회사에 동시에 다니고 있는 사람을 공무원으로 고용해야한다.

승한이는 이 N개의 회사를 합치기 위해서 2개의 회사를 다니는 N-1 명의 사람을 뽑아놓았다. 이 N-1명의 사람을 뽑으면 N개의 회사가 한 개로 합쳐짐은 보장된다.

승한이는 이 사람들을 고용할 때 드는 비용이 너무 아까워서 추가 고용 모집글을 날렸고, K명의 지원자가 도착하였다.

K명의 지원자 중 한 명을 고용하게 되면, 공무원이 N명이 되어 기존의 N-1명의 공무원 중 한명을 해고 하여 새롭게 N-1명을 만든다.

승한이는 i번째 지원자를 뽑을 때, 기존의 N-1명의 공무원 중 한 명을 해고할 것이고, 그렇게 생긴 새로운 N-1명을 고용하는 데 필요한 비용을 알고 싶다.

새로운 N-1명의 공무원이 고용된 후에는 N개의 회사가 한 개로 합쳐져 있어야 한다.

승한이를 도와주자.

Input

첫 번째 줄에는 도시의 수 N, 지원자의 수 K 가 주어진다. ( 1 <= N, K <= 100,000)

두 번째 줄부터 N-1개의 줄에는 기존에 뽑아 놓았던 공무원의 정보 si, ei, ci 가 주어진다.

이는 i번째 공무원이 si, ei번째 회사를 다니며, 고용하는 데에 ci만큼의 비용이 필요하다는 뜻이다.(1 <= si, ei <= N, si != ei, 1 <= ci <= 1,000,000,000)

다음 K개의 줄에는 추가 고용에 지원한 지원자의 정보 Si, Ei, Ci가 주어진다.

이는 i번째 지원자가 Si, Ei번째 회사를 다니며, 고용하는 데에 Ci만큼의 비용이 필요하다는 뜻이다.

Output

K개의 줄에 걸쳐 답안을 출력한다.

i번째 줄에는 i번째 지원자를 고용하고, 기존에 있던 N-1명의 공무원 중 한 명을 해고하여 다시 N-1명의 공무원을 만들었을 때, 새로운 N-1명을 고용하는데에 필요한 최소 비용을 출력한다.

IO Example

입력
5 3
1 3 1
2 3 2
3 4 2
2 5 3
1 2 3
1 4 5
4 5 4


출력
9
11
9

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]