Cup of Tea

문제

Abolf lives in Aboland, a country consisting of $nn$ cities and $n-1n\; -\; 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 $11$ to $nn$.

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 $kk$ units of happiness. However, each time Abolf travels through the $ii$^th road, he must pay $c_{i}c\_i$ coins as toll which causes him to lose $c_{i}c\_i$ units of happiness.

Abolf currently resides in city $11$ 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 $tt$ (for $2\le t\le n2\; \backslash le\; t\; \backslash le\; n$), Abolf wants to know what is the minimum amount of coins he should pay to reach city $tt$ 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 $nn$ and $kk$ ($2\le n\le 3\cdot {10}^{5}2\; \backslash le\; n\; \backslash le\; 3\; \backslash cdot\; 10^5$, $1\le k\le {10}^{9}1\; \backslash le\; k\; \backslash 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-1n\; -\; 1$ lines contains three space-separated integers $v_{i}v\_i$, $u_{i}u\_i$, and $c_{i}c\_i$ ($1\le v_i,u_i\le n1\; \backslash le\; v\_i\; ,\; u\_i\; \backslash le\; n$, $1\le c_i\le {10}^{9}1\; \backslash le\; c\_i\; \backslash le\; 10^9$, $u_i\mathrm{\ne }{v}_{i}u\_i\; \backslash ne\; v\_i$) indicating that the $ii$^th road connects city $u_{i}u\_i$ and city $v_{i}v\_i$, and Abolf should pay $c_{i}c\_i$ coins each time he travels through this road. The last line contains $nn$ integers $a_1,a_2,\dots ,a_{n}a\_1,\; a\_2,\; \backslash dots\; ,\; a\_n$ ($0\le a_i\le 10\; \backslash le\; a\_i\; \backslash le\; 1$). If $a_i=1a\_i\; =\; 1$, there is an Abolbucks branch in city $ii$. It is guaranteed that $a_1=1a\_1\; =\; 1$.

출력

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