23181번 - Utilitarianism 2 다국어

To fight the COVID-19 pandemic, vaccines must be transported efficiently to the people. There are $n$ vaccine manufacturers (numbered from $1$ to $n$), $m$ hospitals (numbered from $1$ to $m$), and $k$ agents (numbered from $1$ to $k$) in RUN-land. Agents deliver vaccines from manufacturers to hospitals. The $i$-th agent has an assignment to deliver $c_i$ vaccines from manufacturer $a_i$ to hospital $b_i$. The assignments are designed such that for any two agents, they must be assigned to different manufacturers or different hospitals, or both.

RUN-land has a very important law: no manufacturer can use more than one agent, and no hospital can receive vaccines from more than one agent. It is possible that not all agents will be called on to complete their assignments.

The agents play an important role in this battle with the pandemic. Therefore, they should be rewarded reasonably based on their merits. The principle known as Vickery-Clarke-Groves pricing states the social value of each agent as follows. Given a set of participating agents $S$, let $f(S)$ be the maximum possible count of vaccines delivered to hospitals, subject to the law stated above. Let $U$ be the set of all agents. Then the social value of each agent $e$ is $f(U) - f(U \setminus \{e\})$. 

In short, given that the agents always act to maximize the number of vaccines that are delivered, the social value of the agent corresponds to the decrease in the number of vaccines delivered if that agent does not participate.

Please determine the social value for all agents.

The first line contains three integers $n$, $m$, and $k\ (1 \le n, m \le 2\,000$, $1 \le k \le \min(8\,000, n \times m)$.

The next $k$ lines contains three integers $a_i$, $b_i$, and $c_i\ (1 \le a_i \le n$, $1 \le b_i \le m$, $1 \le c_i \le 10^{12})$. 

If $i \neq j$, $(a_i, b_i) \neq (a_j, b_j)$.

Output $k$ lines, where the $i$-th line contains a single integer denoting the social value of agent $i$.