题目描述

给定一个 n 个顶点 m 条边的有向有权图，结点编号从 1 至 n，权值是正整数。 对于 u=1,2,3,…n，依次输出从u出发的所有边的权值之和。 即先输出从顶点1出发的所有边的权值之和，再输出从顶点2出发的所有边的权值之和，依次类推，直到输出顶点n的权值和……

输入格式

第一行输入两个正整数 n 和 m，表示图的顶点数和边数。1≤n≤1000，1≤m≤10^5。 第二行开始，往后 m 行，每行输入3个以空格隔开的正整数 u,v,w，表示从顶点u到顶点v有一条权值是w的边。 1≤w ≤10^5。 数据保证图无重边。

输出格式

输出 n 行，每行1个整数。第 i 行输出从顶点 i 出发的所有边的权值之和。 注意，如果一个结点不存在出边，输出权值之和为0。

样例

输入样例 1

3 4
1 3 12
1 2 90
3 2 23
3 1 17

输出样例 1

102
0
40

输入样例 2

3 9
1 3 12
2 3 23
3 3 41
1 2 19
2 2 5
3 2 9
1 1 21
2 1 11
3 1 17

输出样例 2

52
39
67

输入样例 3

4 5
1 3 34
1 2 3
2 3 14
4 2 35
4 3 21

输出样例 3

37
14
0
56