#include<bits/stdc++.h>
using namespace std;
struct E{
	int x,y,w;
	E(int x,int y,int w):x(x),y(y),w(w){}
};

const int maxn = 0xffffffff;
vector<E> edge,ans;
int n;
int g[2048][2048];

int fa[2300],f[2400],dis[2400];
int bo,d;
int p[2300];
vector<pair<int,int> > e[2300];

bool cmp(E a,E b){
	return a.w<b.w;
}

void dfs1(int now,int pre){
	p[now]++;
	if (p[now]==2 && bo==0) bo=now;
	for (int i=0;i<e[now].size();i++){
		int u = e[now][i].first;
		if (u!=pre) dfs1(u,now);
	}
}

void dfs2(int now,int pre,int ans,int pur){
	if (now == pur){
		d+=ans;
		return ;
	}
	for (int i=0;i<e[now].size();i++){
		int u = e[now][i].first;
		if (u!=pre) dfs2(u,now,ans+e[now][i].second,pur);
	}
}

int find(int now){
	if (now==fa[now]) return now;
		else {
		fa[now]=find(fa[now]);
		//dis[now]=dis[now]+dis[fa[now]];
		return fa[now];
	}
}

int main(){
	int cas=0;
	while(scanf("%d",&n)!=EOF){
		cas++;
		//memset(g,0,sizeof(g));
		edge.clear();
		for (int i=1;i<=n;i++){
			for (int j=1;j<=n;j++){
				int x;
				scanf("%d",&x);
				g[i][j]=x;
				if (j>i) edge.push_back(E(i,j,x));
				//g[i][j]=maxn;
			}
		}
		
		sort(edge.begin(),edge.end(),cmp);
		
		for (int i=1;i<=n;i++) fa[i]=i;
		for (int i=1;i<=n;i++) e[i].clear();
		
		ans.clear();
		E ext(1,2,g[1][2]);
		int t=0;
		for (int i=0;i<edge.size();i++){
			E now = edge[i];
			int x = find(now.x);
			int y = find(now.y);
			if (x!=y){
				fa[y]=x;
				e[now.x].push_back(make_pair(now.y,now.w));
				e[now.y].push_back(make_pair(now.x,now.w));			
				ans.push_back(now);
			}else{
				if (t==1){continue;}
				bo=0;
				d=0;
				memset(p,0,sizeof(p));
				//dfs1(now.x,-1);
			//	dfs1(now.y,-1);
				dfs2(now.x,-1,0,now.y);
				//dfs2(now.y,-1,0);
				
				//for (int j=1;j<=n;j++)
				//	if (p[j]==1) d+=dis[j];
				//if (bo) d=abs(dis[now.x]-dis[now.y]);
				//	else d=dis[now.x]+dis[now.y];
				if (d>now.w){
					ans.push_back(now);t++;
				}else ext=now;
			}
		}
		if (cas>1) printf("\n");
		if (ans.size()<n) ans.push_back(ext);
		//cout << ans.size()<<endl;
		for (int i=0;i<ans.size();i++){
			printf("%d %d %d\n",ans[i].x,ans[i].y,ans[i].w);
		}
		
	}
	return 0;
}