240890 - 带权图的邻接矩阵

题目描述

一个带权有向图中有 n 个点(编号为1∼n),以及 e 条边。按照以下要求输出图中每个点的邻接点信息:

1.每个点的邻接点是指从该点出发,有路径可以直接到达的点。

2.输出每个点的邻接点时,按照结点编号从小到大的顺序排列。

3.如果某个点没有邻接点,则说明该点没有连接出边。

输入

第一行包含两个整数 n 和 e , 分别表示图中有 n 个点和 e 条边。(其中 n <= 1000, e <= 100,000)

接下来 e 行,每行包含三个整数 x,y 和 t,表示从 点x 到 点y 存在一条有向边,这条边的权值为 t。(其中 x,y<=n 且保证任意两点之间最多只有 1 条边,所有边的权值均小于 1e6)

输出

对于每个点,按照编号从小到大的顺序输出其邻接点信息(即可以直接通过一条有向边到达的点)

如果某个点没有邻接点,则不需要输出这个点的信息。

样例

输入

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

输出

1
2 3
3 9
4 0
2
3 5
4 1
3
5 7
4
3 2
5 1
标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 82
通过人数 38
金币数量 2 枚
难度 入门


上一题 下一题