捷克公路网由 $N$ 个城市和 $N-1$ 条已知长度（单位：千米）的道路组成。我们已知任意两个城市之间都存在唯一的一条路径。此外，每个城市都有且仅有一个加油站。

某天，有几个人决定开车旅行。总共有 $N^2$ 辆车在行驶。奇怪的是，对于每一对有序城市 $(a, b)$，恰好有一辆车从城市 $a$ 开往城市 $b$，并沿着这两座城市之间唯一的路径行驶。由于捷克人使用的都是斯柯达汽车，每辆车的油箱容量均为 $K$ 升，且每行驶一千米消耗一升汽油。出发前，每辆车的油箱都是满的。此外，捷克人的行为非常可预测。由于他们比较懒，只有在没有足够的汽油到达下一个城市时才会加油（进入城市时油箱为空也是允许的）。一旦他们被迫在某个加油站停车，他们总是会将油箱加满。

捷克税务部门想知道一天中每座城市的加油站有多少辆车停下来加油。鉴于这种可预测的行为，你应该能够轻松计算出结果。

输入格式

第一行包含两个空格分隔的整数 $N$ 和 $K$，分别表示城市数量和每辆车的油箱容量。接下来的 $N-1$ 行描述道路。每行包含三个空格分隔的整数 $u_i, v_i$ 和 $l_i$，其中 $u_i$ 和 $v_i$ 是第 $i$ 条道路连接的城市编号，$l_i$ 是该道路的长度（单位：千米）。城市编号从 $0$ 到 $N-1$。保证任意两个城市之间都存在唯一的一条路径。

输出格式

你应该输出 $N$ 行，包含每座城市加油站的停车次数，按城市 $0$ 到城市 $N-1$ 的顺序排列。

样例

样例输入 1

3 1
0 1 1
1 2 1

样例输出 1

0
2
0

说明 1

有三座城市排成一线，道路长度均为 1，油箱容量为 1 升。只有往返于两端城市的车辆会在中间城市停车。

样例输入 2

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

样例输出 2

0
3
3
12
8
0

说明 2

这次有 6 座城市排成一线，油箱容量为 2 升。许多车辆需要在城市 3 和 4 停车。这是合理的，因为城市 3 和 4 之间连接的道路长度为 2 千米。

数据范围

• $2 \le N \le 70\,000$
• $1 \le K \le 10^9$
• $0 \le l_i \le K$ （对于每个 $0 \le i \le N-2$）

子任务

令 $D$ 表示连接到单个城市的最大道路数量。

1. (18 分) $N \le 1\,000, K \le 1\,000$
2. (8 分) $D \le 2$ 且 $l_i = 1$ （对于每个 $0 \le i \le N-2$）
3. (10 分) $D \le 2$
4. (12 分) $K \le 10, D \le 10$
5. (17 分) $K \le 10$
6. (35 分) 无附加限制