City Road Upgrade Optimization

Mayor Mirko lives in a city with n communities connected by n-1 bidirectional roads forming a tree. Each road initially allows vehicles to travel at speed \(v_i\). Upgrading a road costs \(c_i\) euros and increases its speed to \(s_i\). There are q citizens, and the i-th citizen suggests spending \(e_i\) euros on upgrading the roads along the unique path between communities \(a_i\) and \(b_i\>.

For each suggestion, Mirko wants to know: if he can spend at most \(e_i\) euros on upgrading some roads along the path, and he wants the minimum speed on that path to be as high as possible, what is the maximum achievable minimum speed?

Formally, for a chosen threshold \(T\), for each road on the path from \(a_i\) to \(b_i\), you can decide whether to upgrade it. If you do not upgrade a road, its speed remains \(v_i\); if you upgrade, its speed becomes \(s_i\) at a cost of \(c_i\). In order for the minimum speed on the path to be at least \(T\), every road must have speed at least \(T\) after the decision. That is, for each road on the path, if \(v_i \ge T\) you may leave it as is, otherwise if \(s_i \ge T\) you can upgrade it by paying \(c_i\), and if neither is true then \(T\) is unachievable. Your task is to determine the maximum \(T\) such that the total cost required does not exceed \(e_i\>.

You are given the structure of the city and must answer all queries.

inputFormat

The first line contains two integers n and q — the number of communities and the number of queries.

The next n-1 lines each contain five integers u, v, \(v_i\), \(c_i\), and \(s_i\) describing a road between communities u and v with current speed \(v_i\), upgrade cost \(c_i\), and upgraded speed \(s_i\).

The next q lines each contain three integers a_i, b_i, and \(e_i\) representing a query between communities \(a_i\) and \(b_i\) with a budget of \(e_i\) euros.

outputFormat

For each query, output a single integer: the maximum achievable minimum speed on the path from community \(a_i\) to \(b_i\) if at most \(e_i\) euros are spent on upgrades.

sample

3 3
1 2 10 5 20
2 3 15 10 25
1 3 5
1 3 10
2 3 0

15
15
15