Background

Professor Z is the teacher of Class C.

Professor Z recently discovered a magical phenomenon: all of his students secretly have a crush, but none of them dares to confess.

As someone who has been through it, Professor Z of course understands the most real and pure thoughts in each student's heart, as well as what they believe to be love. Professor Z recalled his first love, Jiao Tailang (pinyin), and he did not want his students to lose color in their youth. So, Professor Z took the risk of being fired and主动 helped the students express their feelings.

Then Professor Z was fired.

Problem Description

There is an inward directed unicyclic graph with $n$ nodes (weakly connected is guaranteed). Each edge has a weight. There is also a fixed parameter $k$.

Since the graph is inward, a node $x$ may have nodes that it cannot reach directly. However, we may reverse some directed edges in the graph so that $x$ can reach every node. If a node $x$ needs to reverse at least $k$ edges in order to reach $y$, then $y$ is called a "Ride the Wind and Waves" node of $x$. After reversing the minimum number of edges so that $x$ can reach $y$, on the shortest path from $x$ to $y$, define $F(x, y)$ as the sum of weights of the non-reversed edges, and $R(x, y)$ as the sum of weights of the reversed edges.

If $y$ is a "Ride the Wind and Waves" node of $x$, then there is a value $G(x, y)$ representing the wave value from $x$ to $y$, defined as $G(x, y) = F(x, y) \times R(x, y)$.

For each node $i$, output the value of $\sum G(i, y)$, where $y$ ranges over all "Ride the Wind and Waves" nodes of $i$.

Input Format

The first line contains two positive integers $n, k$, representing the size of the unicyclic graph and the comparison parameter.

The next $n$ lines each contain three positive integers $u, v, w$, indicating that there is an edge $(u, v, w)$ in the graph, where the starting node is $u$, the ending node is $v$, and the weight is $w$.

Output Format

Output $n$ lines, each containing one positive integer, representing for each node the sum of wave values to all of its "Ride the Wind and Waves" nodes.

7 1
1 4 3
2 1 2
3 1 6
4 3 4
5 2 4
6 4 1
7 5 2

3
5
105
160
9
176
11

7 1
1 2 3
2 3 2
3 1 2
4 1 3
5 4 2
6 2 1
7 6 4

18
32
46
36
48
40
72

Hint

Sample Explanation #1

Take the answer for node $3$ as an example. The unicyclic graph looks like the figure below:

We can see that $2, 5, 6, 7$ are "Ride the Wind and Waves" nodes of $3$. Compute the answer:

• $G(3, 2) = 6 \times 2 = 12$.

• $G(3, 5) = 6 \times 6 = 36$.

• $G(3, 6) = 9 \times 1 = 9$.

• $G(3, 7) = 6 \times 8 = 48$.

So $\sum G(3, j) = 12 + 36 + 9 + 48$, and the answer is $105$.

Constraints

This problem uses bundled testdata.

• Subtask 1 (5 points): $1 \leqslant n \leqslant 10$, includes special property.
• Subtask 2 (10 points): $1 \leqslant n \leqslant 5000$, includes special property.
• Subtask 3 (25 points): $1 \leqslant n \leqslant 10^5$, includes special property.
• Subtask 4 (60 points): $1 \leqslant n \leqslant 10^6$, no special restrictions.

Special property: the number of nodes on the cycle is guaranteed to be within $10^3$.

For all testdata, $1 \leqslant n \leqslant 10^6$, $1 \leqslant k \leqslant 10$, and the answer is guaranteed not to exceed $10^{18}$.

Translated by ChatGPT 5