Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

COVID-19 Outbreak

By Peregrine_Falcon · Limits 3s, 512 MB

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 NN cities in Atlantis. They are connected through N1N - 1 bi-directed roads. It is possible to reach from any city to another using exactly one path. Cities are numbered from 1 to NN. The city Athens is numbered by an integer ZZ. For each i from 1 to NN there are XiX_i food trucks in city ii.

Due to the lockdown, no road is allowed to pass more than YY trucks. This limit of YY 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 NN and ZZ (1ZN1061 \le Z \le N \le 10^6). Each of the next N1N - 1 lines contains three integers UU, VV (1U,VN1 \le U, V \le N) and YY (1Y1061 \le Y \le 10^6) meaning there is a road between city UU and VV and the capacity of that road is YY. Next line contains N integers (0Ni1060 \le N_i \le 10^6). The ithi_{th} integer indicates the number of food trucks in the city ii.

Output

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

Sample

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

Discussion

Statistics


82% Solution Ratio

dontquitEarliest, Mar '20

EgorKulikovFastest, 0.6s

user.479611Lightest, 86 MB

user.055255Shortest, 572B

Submit

Login to submit

Editorial

Run BFS from source Z. Save distance of each node from Z. For each node, set the flow of this node =...

Related Contests