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 .

#### Constraints

##### Subtask 1 [10%]

##### Subtask 2 [90%]

No additional constraints.

#### 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`

## Comments