## An Animal Contest 5 P6 - Larry Finally Uses His Magical Powers

View as PDF

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types

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 ?

#### Input Specification

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 Specification

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

0 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