Description

Crystals are scattered all along the road to the summit.

In a cluster of crystals, Madeline finds an unusual crystal cave, with colorful gems embedded inside.

After observing, Madeline realizes that these gems form a wonderful mechanism: as long as the gems collect enough magic power, the mechanism can be activated and the Crystal Heart can be obtained.

More specifically, in this huge cave there are $n$ gems. Each gem is embedded in a tree structure that is exactly the same in shape but independent from the others. To be even more specific, there are $n$ identical tree structures $T$ in the cave. The tree structure $T$ has $n$ nodes, and the $i$-th gem is embedded at node $i$ of the $i$-th tree structure $T$.

Madeline can push a gem so that it slides along the tree. After the gem passes through an edge, that edge will be closed, and the magic power stored on that edge will be accumulated into the gem. (Reminder: the tree structures containing these $n$ gems are independent. This means that closing an edge in one tree will not cause the same edge to be closed in other trees.)

A gem has a limit on how much magic power it can store. More specifically, each gem can store only $mod$ magic power. Once it exceeds this upper bound, the magic power overflows. You can treat this as taking the stored magic power modulo $mod$.

Madeline wants to know the maximum magic power that the gem embedded at each vertex can store in the end. Can you help her?

Input Format

The first line contains two integers $n$, $mod$, representing the number of nodes in the tree structure and $mod$.

The next $n-1$ lines each contain three integers $u, v, w$, describing an undirected edge in the tree structure that connects $u$ and $v$ with energy value $w$ ($0 \leq w < mod$). (Note that closing an edge works in both directions, which means you cannot go back along that edge.)

It is guaranteed that these edges form a tree.

Output Format

Output $n$ lines, each line containing $n$ integers. The $i$-th integer represents the maximum magic power that the gem embedded at vertex $i$ can store.

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

15
15
15
10
15

Hint

In the "Special Convention", "a chain" means that the $i$-th edge of the tree structure connects node $i$ and node $i+1$.

For all testdata, $0 \leq w < mod$.

It is guaranteed that all input edges form a tree.

For test points $1$ to $6$, the time limit is $1s$.

For test points $7$ to $12$, the time limit is $2s$.

For test points $13$ to $20$, the time limit is $3s$.

Translated by ChatGPT 5