Minimize The Summation
Problem Description

Given a tree containing A nodes rooted at node 1.

Find the minimum value of the sum of Distance(1, i) where i varies from 1 to A using atmost C operations. In other words, find the minimum value of Distance(1, 1) + Distance(1, 2) + Distance(1, 3) ... upto Distance(1, n) using atmost C operations.

In one operation you can change the weight of any edge to zero.

Nodes are connected by A-1 edges. Given an array B where B[i]0 is connected to node B[i][1] with edge of weight B[i][2].

NOTE:

Distance between node 1 and node i = Sum of weight of edges between them.
The global variables need to be cleared because the code will run for multiple test cases.
Return your answer modulo 109 + 7.

Problem Constraints
1 <= A <= 105
1 <= B[i][0] <= A
-109 <= B[i][1] <= 109
0 <= C <= A-1

Input Format
First argument is an integer A denoting the number of nodes.
Second argument is a 2D integer array B of size (A-1)*3 represeting the edges of the tree.
Third argument is an integer C representing the maximum number of operations you can perform.

Output Format
Return an integer denoting the minimum possible value of the sum.

Example Input
Input 1:

A = 5
B = [
[1, 2, 11]
[1, 3, 5]
[2, 4, 3]
[2, 5, 14]
]
c = 1
Input 2:

A = 5
B = [
[1, 2, 10]
[1, 3, 5]
[1, 4, 9]
[2, 5, 11]
]
C = 0

Example Output
Output 1:

22
Output 2:

45

Example Explanation
Explanation 1:

Given Tree:
1
/
2 3
/
4 5

Change the weight of edge connecting 1, 2 to 0.
Sum = Distance(1, 1) + Distance(1, 2) + Distance(1, 3) + Distance(1, 4) + Distance(1, 5).
= 0 + 0 + 5 + 3 + 14 = 22.

Explanation 2:

Given Tree:
1
/ | \
2 3 4
/
5
You can not change the weight of any edge as C = 0.
Sum = Distance(1, 1) + Distance(1, 2) + Distance(1, 3) + Distance(1, 4) + Distance(1, 5).
= 0 + 10 + 5 + 9 + 21 = 45.