COVID-19 Outbreak

COVID-19 outbreak in Atlantis is so bad that the government is forced to lock down the whole country. Athens, the capital of Atlantis is an overpopulated city. The situation here is very severe. People are having a shortage of food as a result of the lockdown. So, all other cities decided to send food to Athens by trucks.

There are $N$ cities in Atlantis. They are connected through $N - 1$ bi-directed roads. It is possible to reach from any city to another using exactly one path. Cities are numbered from 1 to $N$. The city Athens is numbered by an integer $Z$. For each i from 1 to $N$ there are $X_i$ food trucks in city $i$.

Due to the lockdown, no road is allowed to pass more than $Y$ trucks. This limit of $Y$ differs from road to road. You have to find the maximum total number of food trucks Athens can have, if every city sends food trucks in the optimal way.

Input

First line of input contains two integers $N$ and $Z$ ($1 \le Z \le N \le 10^6$). Each of the next $N - 1$ lines contains three integers $U$, $V$ ($1 \le U, V \le N$) and $Y$ ($1 \le Y \le 10^6$) meaning there is a road between city $U$ and $V$ and the capacity of that road is $Y$. Next line contains N integers ($0 \le N_i \le 10^6$). The $i_{th}$ integer indicates the number of food trucks in the city $i$.

Output

Print one integer, the maximum possible number of food trucks that Athens can have.

Sample

5 1
1 4 3
1 2 6
2 5 10
2 3 2
7 4 6 5 2

16