题目描述

给定一个 n 个顶点 m 条边的无向有权图，顶点编号从 1 至 n。按照从小到大的顺序，依次输出每个点的所有边的权值之和。

输入格式

第一行输入两个正整数 n 和 m，表示图的顶点数和边数。1≤n≤1000，1≤m≤10^5。 第二行开始，往后 m 行，每行输入3个以空格隔开的正整数 u,v,w，表示 u,v 顶点之间有一条边直接相连（u、v是顶点编号，数值范围是1~n）,w是这条边的权值。 本题测试数据确保任意两点之间最多只有1条边、且数据合法，不存在x点到x点有边的情况。

输出格式

按照从小到大的顺序，先输出每个点的编号（如果该点没有边，则该点不输出），空格隔开后输出该点的所有边的权值之和，输出格式请参考本题的样例。

样例

输入样例 1

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

输出样例 1

1 9
2 14
3 19
4 19
5 9

输入样例 2

2 1
1 2 5

输出样例 2

1 5
2 5

输入样例 3

4 3
1 2 10
1 3 20
1 4 30

输出样例 3

1 60
2 10
3 20
4 30