P9706 "TFOI R1" Ride the Wind and Waves

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.

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$.

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 $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.

#### 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