Abolf 住在 Aboland，这是一个由 $n$ 个城市和 $n - 1$ 条双向道路组成的国家。在 Aboland，人们可以使用这些道路从任意城市旅行到其他任意城市。Aboland 的城市编号为 $1$ 到 $n$。

Abolbucks 是一家跨国连锁茶馆，提供世界上最好的茶。当 Abolf 进入一个设有 Abolbucks 分店的城市时，他会喝一杯茶，其幸福感会立即达到 $k$ 个单位。然而，每次 Abolf 经过第 $i$ 条道路时，他必须支付 $c_i$ 个金币作为过路费，这会导致他失去 $c_i$ 个单位的幸福感。

Abolf 目前居住在城市 $1$，并想规划他的暑期旅行。如果在旅行期间的任何时刻，Abolf 的幸福感降到零以下，他会立即停止旅行。对于每个城市 $t$（$2 \le t \le n$），Abolf 想知道，在确保他的幸福感在任何时候（包括在目的地）都保持非负的前提下，到达城市 $t$ 所需支付的最少金币数是多少。

他请你为除他的家乡城市以外的每个城市计算这个金额。请注意，每个目的地都应单独考虑。此外，在旅行期间，他可以多次访问同一个城市。

输入格式

输入的第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 3 \cdot 10^5$，$1 \le k \le 10^9$），分别表示 Aboland 的城市数量以及 Abolf 喝一杯茶后的幸福感。

接下来的 $n - 1$ 行，每行包含三个空格分隔的整数 $v_i$、$u_i$ 和 $c_i$（$1 \le v_i, u_i \le n$，$1 \le c_i \le 10^9$，$u_i \neq v_i$），表示第 $i$ 条道路连接城市 $u_i$ 和城市 $v_i$，且 Abolf 每次经过这条道路时需要支付 $c_i$ 个金币。

最后一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 1$）。如果 $a_i = 1$，则表示城市 $i$ 设有 Abolbucks 分店。保证 $a_1 = 1$。

输出格式

在输出的唯一一行中，你应该输出 $n - 1$ 个整数。第 $i$ 个数字应该是 Abolf 从城市 $1$ 到达城市 $i + 1$ 所需的最少金币数。如果无法在幸福感始终保持非负的情况下到达城市 $i + 1$，则对该城市输出 $-1$。

样例

输入样例 1

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

输出样例 1

-1 3 2 3 6