Problem Description

Given an undirected tree with $n$ nodes, each edge has a weight. There is a starting node $S$ and an ending node $T$ on the tree.

A piece can move between nodes along the edges, and the cost of each move is equal to the weight of the traversed edge.

If the piece is currently at node $u$ and there is an edge with weight $w$ connecting node $u$ and node $v$, then G can spend $w$ coins to move the piece to node $v$. The game starts with the piece at node $S$, and G needs to move the piece to node $T$.

G decides to use a cheat code that allows him to teleport the piece from the current node to any node that is not directly connected to the current node, at a cost of $k$ coins. G can use this cheat code at most once.

Y, being righteous, can block at most $m$ possible teleport routes before G starts his move. If Y blocks the teleport route from node $x$ to node $y$, the cost for G to teleport the piece from node $x$ to node $y$ will become $10^9$. The cheat code is powerful, and G knows which routes Y has blocked. Note that the teleport routes are one-way; blocking the route from node $x$ to node $y$ does not affect G's ability to teleport from node $y$ to node $x$.

Interestingly, G not only controls the piece to move to node $T$ but also wants to minimize the total number of coins spent; while Y wants to maximize the number of coins G spends.

If both players adopt optimal strategies, how many coins will G spend in total?

Input Format

The first line contains five integers $n, m, k, S, T$.

The next $n-1$ lines, each containing three positive integers $u_i, v_i, w_i$, represent an edge with weight $w_i$ connecting node $u_i$ and node $v_i$.

Output Format

Output a single integer, which is the number of coins G will spend under optimal strategies for both players.

Sample Input and Output

Input Sample #1

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

Output Sample #1

14

Input Sample #2

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

Output Sample #2

12

Notes/Hints

「Sample Explanation #1」

One possible scenario: Y blocks the teleport routes from node $1$ to node $2$ and from node $4$ to node $2$.

G moves the piece from the starting node to node $4$, then teleports from node $4$ to node $3$, and finally reaches the ending node, spending a total of $14$ coins.

「Data Range」

This problem uses batched testing.

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

For all test data, $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$. Node numbers range from $1$ to $n$.

August 4, 2024: Added samples to Subtask #0.

见题面 Input 部分

见题面 Output 部分