Description

通往山顶的路上水晶遍布。

在晶簇中，Madeline 发现了一个不同寻常的水晶洞穴，洞穴中镶嵌着五彩斑斓的宝石。

经过 Madeline 的观察，她发现这些宝石形成了一个奇妙的机关，只要让宝石收集到足够的魔力，就能打开机关，拿到水晶之心。

具体来说，在这个巨大的洞穴里有着 $n$ 颗宝石，每颗宝石都被镶嵌在形态结构完全相同但相互独立的树形结构里。更具体地，在这个洞穴里有 $n$ 个相同的树形结构 $T$，树形结构 $T$ 有 $n$ 个节点，而第 $i$ 颗宝石被镶嵌到了第 $i$ 个树形结构 $T$ 的第 $i$ 号节点上。

Madeline 能够推动宝石从而让宝石在树形结构上滑动。当宝石滑过树形结构的一条边过后，这条边就会被关闭，并且边上储存的魔力就会被积蓄到宝石中。(再次提醒，这 $n$ 颗宝石所在的树形结构是相互独立的，这意味着在一个树形结构中一条边的封闭并不会导致在其他树形结构中这条边也被封闭)

宝石能储存的魔力是有上限的，更具体而言，每颗宝石都只能储存 $mod$ 的魔力，一旦超过这个魔力上界，宝石的魔力就会溢出，你可以认为宝石此时储存的魔力会对 $mod$ 取模。

Madeline 想要知道，镶嵌在每个顶点上的宝石最终最多能储存多少魔力，你能帮帮她吗？

Input Format

第一行为两个整数 $n$，$mod$，表示树形结构的节点数和 $mod$

接下来 $n-1$ 行一行三个整数 $u,v,w$，描述树形结构中一条连接 $u,v$，能量值为 $w$ 的双向边 ($0 \leq w < mod$ )。(注意，封闭一条边是双向的，这意味着你不能走回头路)

保证这些边构成了一棵树。

Output Format

$n$ 行 $n$ 个整数，第 $i$ 个表示镶嵌在第 $i$ 个顶点的宝石最多能储存的魔力。

5 16
1 2 13
2 3 15
3 4 7
3 5 3

15
15
15
10
15

Hint

"特殊约定" 中，"一条链"意味着树形结构的第 $i$ 条边连接第 $i$ 个和第 $i+1$ 个节点。

对于所有数据有 $0\leq w<mod$

保证输入的所有边构成一棵树

对于 $1$~$6$ 号测试点，时限为 $1s$

对于 $7$~$12$ 号测试点，时限为 $2s$

对于 $13$~$20$ 号测试点，时限为 $3s$