Description

In the game, Glz is given an unrooted tree with $n$ nodes, with a starting node $S$ and a destination node $T$. Each of the edges has an integer weight.

There is a piece that can be moved between nodes along the edges, with each move costing a number of coins equal to the weight of the edge it passes through.

That is, if there exists an edge connecting nodes $x$ and $y$ with an edge of weight $w$, then Glz can choose to move the piece from $x$ to $y$, paying $w$ coins. At the beginning of the game the piece is at node $S$. Glz needs to make the piece at node $T$ eventually after some moves.

Since Glz was once told that playing a game without using a plug-in is the same as not playing, Glz decides to use a plug-in. Using this plug-in he can spend $k$ coins on moving a piece from the current node to any node not adjacent to the current node. However, Glz can only use this plug-in at most once.

The righteous Ycy cannot sit idly by. Before Glz makes his move, Ycy can block up to $m$ possible teleportation routes. If Ycy blocks the teleportation route from node $x$ to node $y$, the number of coins that it takes for Glz to teleport a piece from node $x$ to node $y$ becomes exactly $10^9$ coins. Due to the power of the plug-in, Glz knows which routes Ycy has blocked after his moving process begins. Note that the blocking procedure is unidirectional, that is, blocking the teleportation route from node $x$ to node $y$ does not affect Glz's teleportation from node $y$ to node $x$.

Interestingly, during the game, Glz wants to minimize the number of coins spent, while Ycy is trying to maximize the number of coins spent.

If both of them adopt their optimal strategy, how many coins will Glz spend in total?

Input Format

The first line of input contains five integers $n$, $m$, $k$, $S$ and $T$ — the number of nodes on the tree, the maximum teleportation routes that can be blocked, the coins that using the plug-in costs, the index of the starting node and the index of the destination node.

Then $n - 1$ lines follow, each line contains three integers $u_i$, $v_i$, $w_i$, representing an edge on the tree connecting nodes $u_i$ and $v_i$, with a weight of $w_i$.

Output Format

Output a single line containing an integer, which denotes the coins that Glz would spend, in the case where both of them adopt their optimal strategy.

4 2 2 1 2
2 3 6
4 1 6
3 1 8

14

9 7 4 1 6
3 8 7
6 8 6
6 7 4
2 5 3
3 2 2
3 9 12
2 1 2
8 4 11

12

Hint

「Sample Explanation #1」

In a possible scenario, Ycy blocks the teleportation routes from node $1$ to node $2$ and from node $4$ to node $2$.

Glz moves the piece from node $1$ to node $4$, and from node $4$ he teleports to node $3$, and then moving to node $2$, spending a total of $14$ coins.

「Constraints」

Subtasks are used in this problem.

• Special Property A: $k = 10^9$.
• Special Property B: $k = 0$.

For all tests, it is guaranteed that $2 \leq n \leq 10^5$, $0 \leq m,k \leq 10^9$, $1 \leq S,T,u_i,v_i \leq n$, $1 \leq w_i \leq 10^9$, $S \neq T$, $u_i \neq v_i$. Nodes are numbered from $1$ to $n$.