There are N cities in the world that are connected by N- 1 roads. All the cities are connected like a tree (a tree is an acyclic undirected connected graph). The cities are marked as 1, 2, ...,N. The natural environment on each road is different. We use wi to indicate the temperature on the i-th road (-109 ≤ wi ≤ 109, 1 ≤ i ≤N - 1, 1 ≤ N ≤ 100,000).
Mia is a happy fairy who loves to travel. She will depart from her city X to city Y(1 ≤ X, Y ≤ N). Mia's body temperature is C(-109 ≤ C ≤ 109). She has prepared a dress with thickness P and K portals (P ≥ 0, 0 ≤ K ≤ 109). For the i-th road (1 ≤ i ≤ N - 1), Mia can only pass the road if and only if the temperature of the road wi is no less than C - P (otherwise she will freeze to death) and no more than C + P (otherwise she will be burned). In the meantime, Mia can use one portal to transfer between two cities connected by one road, no matter how cold or hot the road is. One portal can be used only once to pass one road. Mia wants to bring a dress as thin as possible (i.e. a dress with thickness P as small as possible) so that she can survive her journey from city X to city Y. Please help her find a suitable dress.
The first line is an integer T (1 ≤ T ≤ 5), indicates that there are T-group data.
For each test case, the first line contains two integers N, Q. N is the number of cities. Q is the number of queries (1 ≤ N, Q ≤ 100,000).
The following N - 1 lines describe the roads, the i-th of which contains three integers ui, vi, wi, indicating there is a road between city ui and city vi with temperature wi (1 ≤ ui, vi ≤ N, ui≠vi, -109 ≤ wi ≤ 109, 1 ≤ i ≤ N - 1).
The following Q lines describe the queries, each of which contains four integers X, Y, C, K, meaning the journey starts from X and ends in Y, while Mia's body temperature during this journey is C, carrying K portals (1 ≤ X, Y ≤ N, -109 ≤ C ≤ 109, 0 ≤ K ≤ 109).
For each test case, output Q lines, each of which is the minimum thickness P (P ≥ 0) of Mia's dress during her journey.