River Journey

You are given a country with N cities connected by N-1 bidirectional roads forming a tree (i.e. any two cities can reach each other). All the roads are built along a river. Hence, when traveling along a road, you have two options:

• Walk on land with a cost of a_i to traverse that edge.
• Use a boat. To use the boat you must spend L time to build it at the starting city. Once built, you can travel continuously on multiple roads without disembarking. However, if you choose to get off the boat at any city, you must abandon it and continue on foot thereafter.

When traveling by boat on an edge, the time cost depends on the direction of travel relative to the river flow. Each road is given with parameters \(a_i\) and \(z_i\). If the road is traversed in the native (input) direction (i.e. from the first endpoint to the second endpoint as given in the input) then the boat travel takes time \[ a_i - z_i \] (i.e. traveling downstream). If the road is traversed in the reverse direction it takes time \[ a_i + z_i \] (i.e. traveling upstream). Note that it is guaranteed that both \(a_i-z_i > 0\) and \(a_i+z_i > 0\). Walking always costs \(a_i\) time regardless of the direction.

Your task is to compute the minimum time required to travel from city u to city v by optimally choosing when to walk and when to use the boat (possibly for a contiguous segment of the journey). Remember that if you decide to use a boat, you must pay an extra cost of L time at the start of that boat segment, and once you get off the boat you cannot use it again without rebuilding.

inputFormat

The first line contains two integers \(N\) and \(L\) \((2 \le N \le 10^5,\ 1 \le L \le 10^9)\) — the number of cities and the time cost to build a boat.

Then \(N-1\) lines follow. Each of these lines contains four integers \(u, v, a, z\) \((1 \le u, v \le N,\ 1 \le a, z \le 10^9)\) representing a bidirectional road connecting cities u and v with walking time a and parameter z. In the input the road is given in a fixed order: when traveling from u to v, the boat travel time is \(a - z\) (downstream), and when traveling from v to u, the boat travel time is \(a + z\) (upstream).

The last line contains two integers \(u\) and \(v\) \((1 \le u, v \le N)\) representing the start city and the destination city.

outputFormat

Output a single integer: the minimum time required to travel from u to v optimally using walking and/or boat segments.

sample

5 5
1 2 10 3
2 3 5 1
2 4 6 2
1 5 20 5
3 5

35