题目描述

给定一个 n 个点 m 条边的有向图 G，结点编号从 1 至 n，每条边有一个权值wi。对于 u=1,2,3,…n，依次完成如下要求： 对于 u 的所有出边（即从 u 出发的边），按照权值从大到小的顺序输出出边所指向的节点编号。如果两个出边的权值相同，先输出编号较小的出邻接点。 依次完成的含义是，先按顺序输出 u=1 的出边所指向的点的编号，再按顺序输出 u=2 的出边所指向的点的编号……最后按顺序输出 u=n 的出边所指向的点的编号。

输入格式

第一行输入两个正整数 n 和 m，表示图的顶点数和边数。n≤1,000,000，m≤10,000。 第二行开始，往后 m 行，每行输入3个以空格隔开的正整数 u,v,w，表示 u,v 顶点之间有一条边直接相连（u、v是顶点编号，数值范围是1~n）,w是这条边的权值。 保证每组数据内不存在重边。

输出格式

按照从小到大的顺序，先输出每个点的编号（如果该点没有出边，则该点不输出），再换行输出该点的所有出邻接点（按照权值从大到小的顺序输出，如果两个出边的权值相同，先输出编号较小的出邻接点）。

样例

输入样例 1

50 8
3 1 12
1 2 3
1 7 30
1 21 13
2 4 4
3 4 89
4 5 7
20 9 9

输出样例 1

1
7 21 2
2
4
3
4 1
4
5
20
9

输入样例 2

5 8
1 2 14
2 3 8
2 4 11
1 3 5
1 4 6
4 3 23
3 5 12
4 5 8

输出样例 2

1
2 4 3
2
4 3
3
5
4
3 5

输入样例 3

600 10
4 5 8
1 6 3
200 1 12
5 6 3
5 401 43
3 4 13
48 3 8
5 21 4
2 96 2
2 31 34

输出样例 3

1
6
2
31 96
3
4
4
5
5
401 21 6
48
3
200
1

提示

提示：邻接表内存利用率高，而且可以更方便地进行排序。有权图的邻接表的表项一个结构体，所以涉及对结构体数组的排序。