Larry the magical panda is playing a new game once again! This time, having gotten bored of playing with bamboo sticks, Larry is playing the game on an entire bamboo tree with nodes labeled from to . Being a tree, it has edges and each edge has distance . Furthermore, each node has an additional value associated with it. Being a magical panda, Larry can teleport from a node to any node with distance less than or equal to a given constant from . The teleportation comes at the cost of . For each node , what is the minimum cost for Larry to reach if he starts the game at node ?
Subtask 1 [10%]
Subtask 2 [90%]
No additional constraints.
The first line will contain two integers, and .
The following line will contain integers .
The following lines will each contain two integers, and , denoting an edge between nodes and .
Output space separated integers, the -th of which represents the minimum cost for Larry to reach node .
Sample Input 1
2 1 1 1 1 2
Sample Output 1
Sample Input 2
6 3 100 100 100 100 100 1 1 2 2 3 3 4 4 5 3 6
Sample Output 2
0 100 100 100 101 1