33181번 - Cup of Tea 다국어

문제

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ドル \le t \le 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ドル \le n \le 3 \cdot 10^5,ドル 1ドル \le k \le 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ドル \le v_i , u_i \le n,ドル 1ドル \le c_i \le 10^9,ドル $u_i \ne 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, \dots , a_n$ (0ドル \le a_i \le 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.

제한

힌트