有 $n$ 个人，他们一开始两两之间都还不认识。

但随着时间的推移，逐渐会有一些人开始成为朋友。成为朋友的人又会把他们各自的朋友介绍给对方认识，久而久之，便出现了“朋友的朋友就是朋友”这样的关系。

正因为是朋友，所以只要有一个人在生活中听到了什么八卦传闻，他就会马上给他的所有朋友们分享这些八卦。而朋友们自然也不会闲着，他们会把八卦传给他们各自的朋友……到最后，只要你是一开始分享八卦这个人的直接朋友或者是间接朋友，那么你就会听到这一则八卦传闻。

每条八卦都有可能是炸裂性的，或者是索然无味的。换句话说，每条八卦都拥有一个正整数属性，表示其炸裂程度。

但人们的新鲜感会很快过去，你可以认为每个人一开始听到八卦时会很兴奋，但等到他把八卦分享给他的朋友们之后，便再也不会提起这一条八卦了，即便他之后又交到了新的朋友。你也可以假设分享八卦是一瞬间完成的事情。

现在把人们交朋友的情况以及听到八卦的情况按照时间顺序一一告诉你，请你求出到最后每个人所听到的所有八卦传闻的炸裂程度之和是多少。

输入格式

第一行包含两个整数 $n,m$，分别表示总人数和情况总数。每个人从 $1$ 至 $n$ 编号。

接下来 $m$ 行，每行三个整数，表示发生了一种情况，按时间顺序给定：

• 如果格式为 $1$ $a$ $b$，则表示编号为 $a$ 和 $b$ 的这两个人成为了朋友。（当 $a=b$ 时，可能只是自恋，请忽略。）
• 如果格式为 $2$ $x$ $y$，则表示编号为 $x$ 的人听到了一条炸裂程度为 $y$ 的八卦。

输出格式

输出一行，包含 $n$ 个整数，依次表示每个人听到的八卦的炸裂程度总和，相邻整数间用一个空格隔开。

样例 1

输入

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

输出

11 11 7

样例解释 1

因为 1 和 2 在听到八卦前就成为了朋友，因此 1 听到的的八卦会分享给 2，2 听到的的八卦也会分享给 1，因此两人听到的八卦总和为 11。

3 听到的八卦无人分享。

样例 2

输入

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

输出

14 11 7

样例解释 2

在 1 听到炸裂程度为 3 的八卦时，和 2 还不是朋友，因此即使后面成为了朋友，2 也无法得知这一八卦。

样例 3

输入

5 10
1 1 2
1 2 4
2 4 7
2 5 8
2 1 4
2 3 4
1 3 5
2 5 9
1 5 4
2 1 7

输出

18 18 20 18 24

样例 4

见下发文件 gossip4.in/out.

数据范围

对于 $25\%$ 的数据，$n\le 20,m\le 100$ 。

对于 $50\%$ 的数据，$n\le 100,m \le 1000$ 。

对于 $75\%$ 的数据，$n\le 1000,m\le 10000$ 。

对于 $100\%$ 数据，$1 \le n \le 10000, 1 \le m \le 100000,1 \le y \le 100$ 。