Problem Description

Xiaoming is doing a network experiment.

He sets up $n$ computers, called nodes, used to send, receive, and store data.

Initially, all nodes are independent, and there are no connections.

Xiaoming can use network cables to connect two nodes. After they are connected, the two nodes can communicate with each other. If there is a cable connection between two nodes, they are called adjacent.

Sometimes Xiaoming tests the current network. He sends a message from a certain node. The message is sent to each adjacent node, and then those nodes forward it to their own adjacent nodes, until all nodes that are directly or indirectly adjacent have received the message. All nodes that send or receive the message will store it. Each message is stored only once.

Given Xiaoming’s process of connecting and testing, compute the total size of messages stored on each node.

Input Format

The first line contains two integers $n$ and $m$, representing the number of nodes and the number of operations. Nodes are numbered from $1$ to $n$.

The next $m$ lines each contain three integers, describing an operation.

If an operation is 1 a b, it means connecting node $a$ and node $b$ with a network cable. When $a = b$, it means adding a self-loop, which has no real effect on the network.

If an operation is 2 p t, it means sending a message of size $t$ from node $p$.

Output Format

Output one line containing $n$ integers, separated by one space, representing the total size of messages stored on nodes $1$ to $n$ after all operations are completed.

4 8
1 1 2
2 1 10
2 3 5
1 4 1
2 2 2
1 1 2
1 2 4
2 2 1

13 13 5 3

Hint

For $30\%$ of the test cases, $1 \le n \le 20$ and $1 \le m \le 100$.

For $50\%$ of the test cases, $1 \le n \le 100$ and $1 \le m \le 1000$.

For $70\%$ of the test cases, $1 \le n \le 1000$ and $1 \le m \le 10000$.

For all test cases, $1 \le n \le 10000$, $1 \le m \le 10^5$, and $1 \le t \le 100$.

Lanqiao Cup 2020, First Round of the Provincial Contest, Group A Problem J (Group B Problem J).

Translated by ChatGPT 5