该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给出一个有向图 ( G )（无重边/自环），请你构造这个图 ( G^2 )。

• 如果在原图 ( G ) 中存在的 2 条有向边 <u,v> 和 <v,w>，则 ( G^2 ) 中存在有向边 <u,w>
• 即 ( G^2 ) 中的边对应于 ( G ) 中恰是两步可以到达的点对

输入格式

第一行包含 2 个整数 N、M，表示该图共有 N 个结点和 M 条有向边（N ≤ 500，M ≤ 100000）

接下来 M 行，每行包含 3 个整数 (u,v,w)，表示有一条长度为 w 的有向边 <u,v>，u 指向 v

输出格式

• N 行，顶点按照 1-N 编号从小到大输出每个点的邻接点构成的边
• 如果对于某个顶点，没有出边，输出空行
• 对于从 u 出发的所有边 <u,v>，输出时按照 v 从小到大排序

数据规模与约定

• 输出需要保证平方图中没有重边
• ( G^2 ) 中可能有自环，也需要输出

样例 1

输入

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

输出

<1,3>
<2,1>
<3,2> <3,4>