Crystal Cave Gem Magic Accumulation

Madeline has discovered an extraordinary crystal cave in the mountains, where crystals are embedded within identical but independent tree structures. In the cave, there are n copies of a tree T, each having n nodes. In the i-th tree, a gemstone is embedded at node i.

Madeline can slide the gemstone along the edges of the tree. Once a gemstone slides past an edge, that edge is closed in that particular tree, and the magic stored on that edge is added to the gemstone. However, each gemstone can only store magic up to a limit. In fact, the magic in each gemstone is taken modulo \(mod\) (i.e. if the accumulated magic exceeds \(mod\), it wraps around by taking the remainder when divided by \(mod\)).

Your task is to help Madeline determine, for each gemstone (located at each vertex in its corresponding tree), what is the maximum magic it can accumulate. In other words, for a tree T and for every starting vertex \(u\) (where the gem is initially placed), compute the maximum value of \(d(u,v)\ \bmod\ mod\) over all vertices \(v\) in T, where \(d(u,v)\) is the sum of the magic values of the edges along the unique simple path from \(u\) to \(v\).

Note: The trees are independent. That is, closing an edge in one tree does not affect the edges in any other tree.

inputFormat

The input begins with a line containing two integers (n) and (mod), where (n) is the number of nodes in the tree and also the number of trees, and (mod) is the modulus for the magic accumulation. This is followed by (n-1) lines, each containing three integers (u), (v), and (w), which denote an edge between nodes (u) and (v) with a magic value of (w). The tree is undirected and the nodes are labeled from 1 to (n).

outputFormat

Output a single line containing (n) space-separated integers. The (i)-th integer represents the maximum magic accumulation (computed modulo (mod)) that the gemstone starting at node (i) can achieve by sliding along a simple path in its respective tree.

sample

3 10
1 2 5
2 3 6

5 6 6