题目背景

instance Applicative [] where
	-- pure :: a -> [a]
	pure x = [x]
	-- (<*>) :: [a -> b] -> [a] -> [b]
	gs <*> xs = [g x | g <- gs, x <- xs]

你确信你是站在三万英尺的高空吗?

题目描述

给定一棵 $n$ 个点的树，1 号点为根。给定一个整数 $m$。

对于树上的每个结点 $u$，有三个参数 $X_u, Y_u, Z_u$，你需要在 $u$ 到根的路径上（不包括 $u$）选择至少 $X_u$ 个结点，在 $u$ 的子树（不包括 $u$）中选择至少 $Y_u$ 个结点。你需要保证你总共选择了 $m$ 个结点。然后，令 $S_1$ 表示 $u$ 上面被选择的结点到 $u$ 的距离和，$S_2$ 表示 $u$ 子树中被选择的结点到 $u$ 的距离和，你需要求出 $|S_1 − S_2 + Z_u|$ 的最小值。

两点之间的距离为两点之间简单路径上的边数。

Notice

询问是每次选的,无解的情况可以参见样例.

输入格式

第一行两个整数 $n, m$。

接下来 $n − 1$ 行，每行两个整数 $u, v$，表示一条树上的边。

接下来 $n$ 行，每行三个整数 $X_i ,Y_i ,Z_i$，表示结点 $i$ 的参数。

输出格式

输出一行 $n$ 个整数表示答案。特别地，若对于一个结点，你无法按要求选择结点，则输出 $−1$。

样例一

input

5 2
1 2
1 3
2 4
2 5
0 0 -1
0 0 0
1 0 1
0 0 2
0 0 1

output

3 0 -1 5 4

样例二

见下发文件中的 applicative/applicative2.in 以及 applicative/applicative2.ans。

限制与约定

对于前 $20\%$ 的数据，$n \le 300$。

对于前 $40\%$ 的数据，$n \le 3000$。

对于前 $60\%$ 的数据，$n \le 10^5$。

对于另外 $20\%$ 的数据，保证对于 $i \in [1, n − 1]$，存在连接 $i$ 与 $i + 1$ 的边。

对于 $100\%$ 的数据，$1 \le n \le 5 \times 10^5$，$0 \le m \le n，|Z_i | \le 10^9$，$X_i , Y_i \ge 0$，保证输入的是一棵树。对于 $u \in [1, n]$，保证 $X_u$ 不超过 $u$ 到根路径上的结点个数（不包括 $u$），保证 $Y_u$ 不超过 $u$ 的子树中的结点个数（不包括 $u$），保证 $X_u + Y_u \le m$。