Description

Abolf 生活在阿博兰德，这是一个由 $n$ 个城市和 $n-1$ 条双向道路组成的国家。在阿博兰德，人们可以通过这些道路从任何一个城市前往任何其他城市。阿博兰德的城市编号从 $1$ 到 $n$。

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

Abolf 目前居住在城市 $1$，并计划他的夏季旅行。如果在旅途中的任何时刻，Abolf 的幸福感降至零以下，他将立即停止旅行。对于每个城市 $t$（$2 \leq t \leq n$），Abolf 想知道，为了确保他在整个旅途（包括目的地）中的幸福感始终保持非负，他需要支付的最小硬币数量是多少才能到达城市 $t$。他请你找出除他家乡城市外每个城市的这个数量。注意，每个目的地应单独考虑。此外，他在旅途中可以多次访问一个城市。

Input Format

输入的第一行包含两个整数 $n$ 和 $k$ ($2 \leq n \leq 3 \cdot 10^5$, $1 \leq k \leq 10^9$)，分别表示阿博兰德的城市数量以及 Abolf 喝了一杯茶后获得的幸福感。接下来的 $n-1$ 行每行包含三个用空格分隔的整数 $v_i$、$u_i$ 和 $c_i$ ($1 \leq v_i, u_i \leq n$, $1 \leq c_i \leq 10^9$, $u_i \neq v_i$)，表示第 $i$ 条道路连接城市 $u_i$ 和 $v_i$，且 Abolf 每次经过这条道路需支付 $c_i$ 硬币。最后一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 1$)。如果 $a_i = 1$，则表示城市 $i$ 有一家 Abolbucks 分店。保证 $a_1 = 1$。

Output Format

在输出的唯一一行中，你应该打印 $n-1$ 个整数。第 $i$ 个数应该是 Abolf 从城市 $1$ 到达城市 $i+1$ 所需的最小硬币数量。如果无法在 Abolf 的幸福感始终保持非负的条件下到达城市 $i+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 3 2 3 6

Hint

翻译由 DeepSeek V3 完成