Problem Background

Little A loves collecting coins. He has a good friend named Little c.

Little c got trapped in a maze while traveling, and upon hearing the news, Little A immediately put down his work on a tree-within-a-tree-within-a-tree-within-a-tree and set out to rescue her.

Problem Description

After some investigation, Little A found that the maze where Little c is trapped consists of $n$ rooms connected by $n-1$ doors, forming a tree structure. Little c is trapped in room $d$.

Little A also noticed that each door has a number $v$ written on it, which represents the number of coins one can collect by passing through that door, but the coins on each door can only be collected once.

The villains who trapped Little c in the maze knew that Little A would come to rescue her, so they set traps in every room, allowing room $i$ to be entered at most $k_i$ times, or else Little A would also get trapped in the maze. Fortunately, Little c informed Little A about these traps when she called for help.

When entering the maze, Little A can choose any initial room $r$ (entering the maze counts as one entry into room $r$). Little A can leave the maze if and only if he is in room $r$.

If Little A enters room $d$, we consider that he has successfully rescued Little c. After rescuing Little c, Little A can continue to move with her in the maze.

Although Little A is not particularly greedy, he still wants to know: under the premise of successfully rescuing Little c and leaving the maze, what is the maximum number of coins he can collect.

Input Format

The first line contains two integers $n$ and $d$ — the number of rooms and the room number where Little c is trapped.

The next $n-1$ lines each contain three integers $x_i, y_i, v_i$ — representing the two room numbers connected by the $i$-th door and the number of coins written on that door.

The next line contains $n$ integers $k_1, k_2, \cdots, k_n$ — representing the maximum number of times each room can be entered.

Output Format

A single integer representing the maximum number of coins Little A can collect.

Sample Input and Output

Input Sample #1

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

Output Sample #1

5

Input Sample #2

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

Output Sample #2

0

Input Sample #3

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

Output Sample #3

12

Input Sample #4

12 6
1 4 33
2 11 51
3 9 100
4 8 7
5 9 35
6 12 30
7 11 58
8 10 65
9 10 59
10 12 9
11 12 72
2 2 2 3 2 1 2 1 2 3 2 2

Output Sample #4

263

Notes

Sample 1 Explanation

An optimal path is: $2 \to 4 \to 2$, which collects a total of $5$ coins.

Sample 2 Explanation

As shown in the diagram, Little A can only land directly in room $4$ and then leave the maze, collecting a total of $0$ coins.

Sample 4 Explanation

An optimal path is: $3 \to 9 \to 10 \to 8 \to 10 \to 12 \to 6 \to 12 \to 10 \to 9 \to 3$, which collects a total of $100 + 59 + 65 + 9 + 30 = 263$ coins.

Data Range and Constraints

This problem uses batched testing.

For $100\%$ of the data, $1 \leq d, k_i \leq n \leq 10^5$, $1 \leq v_i \leq 10^4$.

Source

Sweet Round 04 E

Idea & std: Alex_Wei, Tester: chenxia25

见题面 Input 部分

见题面 Output 部分