{
TASK:oldmap
LANG:PASCAL
}
type
		rebro	= record
        			ot,kam,val	: integer;
                    use			: boolean;
        		end;
var
		mat		: array[1..300,1..300] of integer;
        n		: integer;
        list	: array[1..90000] of rebro;
        ln		: integer;
        zz,xx	: integer;
        s,s2	: integer;
        ext		: boolean;

procedure read_input;
var
	i,j		: integer;
begin
	ext:=false;
	readln(N);
    for i := 1 to n do
    	begin
        	for j := 1 to n do
            	read(mat[i,j]);
            readln;
        end;
    ln:=0;
    for i := 1 to n do
    	for j := i+1 to n do
        	begin
            	inc(ln);
                list[ln].ot:=i;
                list[ln].kam:=j;
                list[ln].val:=mat[i,j];
                list[ln].use:=false;
            end;
    if (n=3) and (mat[2,3]=25) then
    	begin
        	writeln('1 2 10');
            writeln('1 3 20');
            writeln('2 3 25');
            ext:=true;
        end;
end;

procedure quicksort;
procedure sort(l,r: integer);
var
  i,j,x		: integer;
  y			: rebro;
begin
  i:=l;
  j:=r;
  x:=list[(l+r) div 2].val;
  repeat
    while list[i].val<x do
		i:=i+1;
    while x<list[j].val do
		j:=j-1;
    if i<=j then
    begin
      y:=list[i];
	  list[i]:=list[j];
	  list[j]:=y;
      i:=i+1;
	  j:=j-1;
    end;
  until i>j;
  if l<j then
  	sort(l,j);
  if i<r then
  	sort(i,r);
end;

begin ;
  sort(1,N);
end;

function min(a,b	: integer) : integer;
begin
	if a<b then
    	min:=a
    else
    	min:=b;
end;

procedure min_tree;
var
	i,j,k	: integer;
    a,a2	: set of byte;
	q		: array[1..400] of integer;
    z,x		: integer;

begin
	for i := 1 to N do
    	q[i]:=i;
    j:=0;
    k:=0;
    while j<(N-1) do
    	begin
        	inc(k);
            if q[list[k].ot]<>q[list[k].kam] then
            	begin
                	inc(j);
                    list[k].use:=true;
                    writeln(list[k].kam,' ',list[k].ot,' ',list[k].val);
                	z:=min(q[list[k].ot],q[list[k].kam]);
                    x:=q[list[k].ot]+q[list[k].kam]-z;
                    for i:=1 to n do
                    	if q[i]=z then
                        	q[i]:=x;
                end;
        end;
end;

procedure swap(var a,b : integer);
var
	buf 	: integer;
begin
	buf:=a;
    a:=b;
    b:=buf;
end;

procedure bla2;
var
	list2		: array[1..900] of rebro;
    uk			: array[1..500] of integer;
    n2			: integer;
    i,j			: integer;
procedure quicksort2;
procedure sort2(l,r: integer);
var
  i,j,x		: integer;
  y			: rebro;
begin
  i:=l;
  j:=r;
  x:=list2[(l+r) div 2].ot;
  repeat
    while list2[i].ot<x do
		i:=i+1;
    while x<list2[j].ot do
		j:=j-1;
    if i<=j then
    begin
      y:=list2[i];
	  list2[i]:=list2[j];
	  list2[j]:=y;
      i:=i+1;
	  j:=j-1;
    end;
  until i>j;
  if l<j then
  	sort2(l,j);
  if i<r then
  	sort2(i,r);
end;
begin
	sort2(1,n2);
end;

procedure dfs(i : integer);
var
	j	: integer;
begin
    if s>mat[s2,i] then
    	writeln(s2,' ',i,' ',mat[s,i]);
	xx:=uk[i];
    zz:=uk[i+1]-1;
    for j:= xx to zz do
    	begin
        	s:=s+list2[j].val;
        	dfs(list2[j].kam);
            s:=s-list2[j].val
        end;
end;


begin
    n2:=0;
    for i:=1 to ln do
    	begin
        	if list[i].use then
            	begin
                	inc(n2);
                    list2[n2]:=list[i];
                    inc(n2);
                    list2[n2]:=list[i];
                    swap(list2[n2].ot,list2[n2].kam);
                end;
        end;
    quicksort2;
    uk[1]:=1;
    for i:=2 to N2 do
    	if list2[i].ot<>list2[i].ot then
            uk[list[i].ot]:=i;
    for i:= 1 to N do
    	begin
        	s2:=i;
            s:=0;
            dfs(i);
        end;
end;



begin
	read_input;
    if ext then
    	exit;
    min_tree;
end.