#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=2001;

int pos,ta[maxn],lin[2*maxn],sd[2*maxn];
void biu(int s,int t)
{
	++pos; lin[pos]=ta[s]; ta[s]=pos; sd[pos]=t;
	++pos; lin[pos]=ta[t]; ta[t]=pos; sd[pos]=s;
}

struct BIAN{
	int w,s,t;
	bool operator< (const BIAN &a) const { return w<a.w; }
};
BIAN bian[maxn*maxn]; int po;

int n;
int mat[maxn][maxn];

//set
int set[maxn];
int fin(int d)
{
	if (d==set[d]) return d;
	return set[d]=fin(set[d]);
}
void uion(int u,int v) { set[u]=v; }

void init()
{
	po=0;
	pos=0;
	for (int i=1;i<=n;i++) ta[i]=0;
}

bool vis[maxn];
int dis[maxn][maxn];
void spfa(int u)
{
	queue<int> q;
	q.push(u); vis[u]=1;
	int v;
	while (!q.empty())
	{
		v=q.front(); q.pop(); vis[v]=0;
		for (int i=ta[v];i;i=lin[i])
			if (dis[u][sd[i]]>dis[u][v]+mat[v][sd[i]])
			{
				dis[u][sd[i]]=dis[u][v]+mat[v][sd[i]];
				if (!vis[sd[i]])
				{
					vis[sd[i]]=1;
					q.push(sd[i]);
				}
			}
	}
}
int main() {
	int TT=0;
	for (;scanf("%d",&n)!=EOF;)
	{
		if (TT) printf("\n");
		TT=1;

		init();
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++)
			{
				scanf("%d",&mat[i][j]);
				bian[++po].w=mat[i][j],
				bian[po].s=i,bian[po].t=j;
				dis[i][j]=i==j?0:2000000000;
			}
		sort(bian+1,bian+1+po);
		for (int i=1;i<=n;i++) set[i]=i;
		for (int i=1;i<=po;i++)
			if (fin(bian[i].s)!=fin(bian[i].t))
				uion(fin(bian[i].s),fin(bian[i].t)),
				biu(bian[i].s,bian[i].t),
				bian[i].w=-1;
		for (int i=1;i<=n;i++) spfa(i);
		bool flag=0;
		for (int i=1;i<=po;i++)
			if (bian[i].w>0)
			{
				if (dis[bian[i].s][bian[i].t]>bian[i].w)
				{
					flag=1;
					biu(bian[i].s,bian[i].t);
					break;
				}
			}
		if (!flag)
		{
			for (int i=1;i<=po;i++)
				if (bian[i].w>0)
				{
					biu(bian[i].s,bian[i].t);
					break;
				}
		}
		//for (int i=1;i<=n;i++) spfa(i);
		for (int v=1;v<=n;v++)
		{
			for (int i=ta[v];i;i=lin[i])
				if (sd[i]!=-1)
				{
					printf("%d %d %d\n",v,sd[i],mat[v][sd[i]]);
					sd[i]=sd[(i+1^1)-1]=-1;
				}
		}
	}
	return 0;
}