题目描述

小珅要把一张带权有向图整理成邻接矩阵。图中共有 $n$ 个顶点和 $m$ 条有向边，顶点编号为 $1$ 到 $n$。

对于一条从 $u$ 指向 $v$、权值为 $w$ 的边，在邻接矩阵中令 $A_{u,v}=w$；如果从 $u$ 到 $v$ 没有边，则令 $A_{u,v}=0$。

除了输出邻接矩阵外，还要统计每个顶点作为起点时，所有出边权值的总和。

输入格式

第一行输入两个整数 $n,m$，分别表示图中顶点的个数和边的条数。

接下来 $m$ 行，每行输入三个整数 $u,v,w$，表示一条从顶点 $u$ 指向顶点 $v$、权值为 $w$ 的有向边。

输出格式

先输出 $n$ 行，每行 $n$ 个整数，表示带权有向图的邻接矩阵。

再输出一行 $n$ 个整数，第 $i$ 个整数表示所有以顶点 $i$ 为起点的边的权值之和。相邻两个整数之间用一个空格分隔。

数据范围与约定

• $1\le n\le 100$；
• $0\le m\le n^2$；
• $1\le u,v\le n$；
• $1\le w\le 10^6$；
• 同一对有序顶点之间至多出现一条边。

可见测试数据

输入数据 1

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

输出数据 1

0 0 3 0 7
0 0 0 6 8
0 0 0 0 2
0 0 0 0 0
0 0 0 0 0
10 14 2 0 0

输入数据 2

1 0

输出数据 2

0
0

输入数据 3

3 3
1 2 5
2 3 7
3 1 2

输出数据 3

0 5 0
0 0 7
2 0 0
5 7 2