Description

从前有张图。图里n个顶点两两之间有N^2种最小割。告诉你这N^2个最小割。还原出这张图。

Format

Input

第一行一个正整数n，表示图的顶点数。

接下来n行每行N个非负整数，第i行第j列的数表示第i个点与第j个点的最小割。

点的编号从1开始。

Vi<=10^5,n<=100

保证vii=0。

Output

第一行一个整数m，表示图的边数。

接下来每行三个整数u,v,z。

表示从“到”存在一条权值为z的边。

l<=u,v<=N

0<Z<=10^9。

m<=n*(n-l)/2。

请注意你给出的图要求联通。

如果无解请输出-l。

若有多解则输出任意一组解。

Samples

3
0 2 2
2 0 2
2 2 0

2
2 3 2
1 3 2