Optimal Teleportation on a Weighted Tree

You are given an undirected tree with n nodes (numbered 1 through n) and n-1 weighted edges. There is no designated root. In addition, two special nodes S and T are given. A game is played as follows: a token starts at node S and must be moved to node T by spending coins. When the token is at node u, it can move to any adjacent node v by spending coins equal to the weight of the edge (u,v).

However, little G is allowed to use an extra move (at most once) via a cheat device. Using this cheat, he may teleport the token from the current node u to any node v that is not adjacent to u. Normally, this teleportation costs k coins. But before the game starts, the adversary little Y is allowed to block at most m teleport routes. If the teleport from node x to node y is blocked, then performing that teleport will cost \(10^9\) coins instead of k coins. Note that teleport routes are directional — blocking the route from x to y does not affect teleportation from y to x.

Little G wants to minimize his total coin expenditure to reach node T, while little Y wants to maximize it. Assuming both play optimally, compute the minimum number of coins that will be spent.

The final cost will be the minimum between the cost of moving along tree edges (i.e. the distance \(d(S,T)\)) and the cost using the teleportation option. When the teleport is used, little Y will block the most beneficial (lowest cost) teleport moves. In effect, if we denote \(A(u)=d(S,u)\) and \(B(v)=d(v,T)\), then any teleport move from u to v (which is valid only if u and v are not adjacent) costs \(A(u)+B(v)+k\). Little Y can block at most m teleport moves (by making their cost \(10^9\)), so under optimal play by both players, the effective teleport option has cost equal to the \((m+1)\)-th smallest valid value of \(A(u)+B(v)\) (plus k).

The answer is therefore computed as:

[ \text{answer} = \min\Bigl(d(S,T), ; \bigl(\text{(m+1)-th smallest valid } (A(u)+B(v))\bigr) + k\Bigr). ]

inputFormat

The first line contains five integers: n m k S T, where n is the number of nodes, m is the maximum number of teleport routes little Y can block, k is the cost of a teleport move, and S and T are the starting and ending nodes respectively.

Each of the next n-1 lines contains three integers u, v and w denoting an undirected edge between nodes u and v with weight w.

outputFormat

Output a single integer, the minimum number of coins little G will spend under optimal play by both players.

sample

4 1 5 1 4
1 2 3
2 3 2
3 4 4

8