题目描述

Abolf lives in Aboland, a country consisting of $n$ cities and $n-1$ two-way roads. In Aboland, one can travel from any city to any other city using these roads. Aboland's cities are numbered from 1 to $n$.

Abolbucks is a multinational chain of teahouses which serves the best tea in the world. When Abolf enters a city with an Abolbucks branch, he drinks a cup of tea and instantly reaches $k$ units of happiness. However, each time Abolf travels through the $i^{th}$ road, he must pay $c_i$ coins as toll which causes him to lose $c_i$ units of happiness.

Abolf currently resides in city 1 and wants to plan his summer trip. If at any point during his trip Abolf's happiness drops below zero, he would stops his trip immediately. For each city $t$ (for $2 \leq t \leq n$), Abolf wants to know what is the minimum amount of coins he should pay to reach city $t$ while making sure that his happiness remains non-negative at all time, including at the destination. He has asked you to find this amount for each city except for his home city. Note that each destination should be considered separately. Also, he may visit a city multiple times during his trip.

输入格式

The first line of input contains two integers $n$ and $k$ ($2 \leq n \leq 3 \cdot 10^5$, $1 \leq k \leq 10^9$), the number of cities in Aboland and Abolf's happiness after he drinks a cup of tea, respectively. Each of the next $n-1$ lines contains three space-separated integers $v_i$, $u_i$, and $c_i$ ($1 \leq v_i, u_i \leq n$, $1 \leq c_i \leq 10^9$, $u_i \neq v_i$) indicating that the $i^{th}$ road connects city $u_i$ and city $v_i$, and Abolf should pay $c_i$ coins each time he travels through this road. The last line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 1$). If $a_i = 1$, there is an Abolbucks branch in city $i$. It is guaranteed that $a_1 = 1$.

输出格式

In the only line of the output, you should print $n-1$ integers. The $i^{th}$ number should be the minimum amount of coins it takes for Abolf to reach city $i+1$ from city 1. If there is no way to reach city $i+1$ such that Abolf's happiness remains non-negative at all time, print $-1$ for that city.

6 3
1 2 4
1 3 3
1 4 2
4 5 1
4 6 2
1 1 0 0 1 0

-1 3 2 3 6