Rescue in the Maze

After some investigation, Little A discovered that the maze in which Little C is trapped consists of \(n\) rooms connected by \(n-1\) doors forming a tree. Little C is trapped in room \(d\). Each door is labeled with an integer \(v\), and when one passes through that door the first time, \(v\) coins are obtained (each door gives coins only once).

However, the villains who trapped Little C have set traps in every room: room \(i\) can be entered at most \(k_i\) times (if exceeded, Little A will also be trapped). Fortunately, Little C told Little A the details of the traps when asking for help.

When entering the maze, Little A may choose any starting room \(r\) (entering room \(r\) counts as one entry). Note that Little A can exit the maze if and only if he is in room \(r\) (the starting room).

If Little A ever enters room \(d\), we say that he has successfully rescued Little C; after the rescue, they may continue to roam the maze together.

Although Little A is not overly greedy, he wonders: under the condition of successfully rescuing Little C and exiting the maze, what is the maximum number of coins he can obtain?

Note on the route: The door coins are obtained only at the first passage through a door, regardless of direction. The closed route that collects coins corresponds to selecting a subset of doors (forming a tree) that is traversed in a round‐trip route starting and ending at \(r\) and containing room \(d\). In such a traversal the door between two rooms contributes to the coin sum exactly once, but the route may require traversing some doors twice. In the corresponding tree of coin‐gaining doors, if a vertex \(i\) is not the starting room then its degree (the number of chosen incident doors) cannot exceed \(k_i\), and if \(i = r\) then its degree must not exceed \(k_r - 1\) (because entering \(r\) at the start counts as one entry).

Your task is to compute the maximum coins Little A can obtain, given the maze description and the trap constraints.

inputFormat

The first line contains two integers \(n\) and \(d\) (\(1 \le n \le \text{small}\)) representing the number of rooms and the room where Little C is trapped.

The following \(n-1\) lines each contain three integers \(u\), \(v\) and \(w\), indicating that there is a door connecting rooms \(u\) and \(v\) with coin value \(w\) (\(w \ge 0\)).

The last line contains \(n\) integers \(k_1, k_2, \dots, k_n\) where \(k_i\) is the maximum number of times room \(i\) can be entered.

All room numbers are 1-indexed.

outputFormat

Output a single integer: the maximum number of coins that Little A can obtain under the conditions of successfully rescuing Little C (i.e. visiting room \(d\)) and exiting the maze (i.e. ending at the starting room \(r\)).

sample

3 2
1 2 10
2 3 5
1 2 1

10