Islands of Anafi

Out of love for greek mythlogy you embarked on a voyage of discovery on the islands of Santorini . You were elated to find the little secret Island of Anafi but little did you know that you have disregarded the wind god Aeoulus by entering the islands most dear to him without persmission . To get out of Anafi you need to collect maximumm resources you can .

The N islands of Anafi are connected to each other via N-1 sea routes . Along each route , you can accquire a certain amount of resources . However if a route is used more than k times .

Given that you can start and end at any of the islands of Anafi , come up iwth a feasible plan that maximise your resource earnings . Note that you can collect your resources along a sea route during its first use . You do not earn extra resources from a route on reusing it .

Example

There are 5 islands in Anafi connecte dto each other via routes as shown in the figure : the first connecting island 1 and 2 and allowing you to accquire 3 units of resources and so on . In this archipelago the best plan for you to start at island 4 visit island 1

(acquiring 5 units of resources along 4--> 1 route ), and then end his path in island 5 (acquiring another 9 units of resources along the 1-->5 route), Having earned a total of 14 uints of resources

Input

First line contains two integers N and k

N - Number of islands in Anafi ( 1 <= N <= 2.10^5)

k - maximum number of times a single route may be used without bein discovered by Aeoulus (1 <= k <= 10^9)

The following N-1 lines decribe the sea routes . Each line contains 3 integers each . u,v (1<u , v<N , u!=v) and c(1 <= k <= 10^9), explaining that sea route connects islands u and v and you can acquire c units of resources along this route

. All sea routes are bidirectional i.e they can be used to travel from island u to v or from island v to u

Output

Output a single value , the maximum amount of resources you can acquire with a feasible plan as decribed in the statement

Sample Input
5 1
1 2 3
2 3 1
1 4 5
1 5 9






Sample Output

14

Robo Data Sharing

In a robot manufacturing company, new robots are manufactured and placed in the form of R x C matrix. Rows are numbered 1 to R and columns are numbered to C
Our robot, Chitti is sitting at the location (%, y) Data is first shared with one of the corner robots (1,1), (R,1),
(1,C) or (R, C) Robot should consume data and pass on to the next robot(right, left, front or back) For robot at the location (x,y) will follow below priority order:
* If there is robot on the right and has not consumed data yet, then pass it right (x, y+1) If there is robot on the left and has not consumed data yet, then pass it left (x, y-1)
* If there is robot on the front and has not consumed data
yet, then pass front (x-1, y) If there is robot on the back and has not consumed data yet, then pass it back (x+1, y)
Shout "Over", If all the robots has consumed data.
Now, Chitti is curious to find out the direction which it will have to pass the or data or shout "Over"

Input

First line consists of single integer T, denoting the number of
test cases.
Each test case has three lines

First line of each test case consists of two space separatedintegers denoting R, C
Second line of each test case denotes the starting position ofdata transfer (Sx, Sy)
Third line of each test case denotes the position of chitti (x,y)

Output:

For each test case return "Left", "Right",
"Front", "Back" or
"Over" depending on whether Chitti will pass the
box or it will
shout "Over"
Constarints:
1 <= T <= 1045
<= R,C <= 1043
1 <= X<=R
1 <= y <= C
Sx = 1 or Sx = R
Sy = 1 or Sy = C

Sample Input:
2
33
11
33
23
13
22
Sample Output:
Over
Right

ADD COMMENT • link