program Floyd;

{$APPTYPE CONSOLE}

uses
  SysUtils;
var a,t:array of array of word;
min,i,j,k,n,t1,t2:word;
begin
  Assign(Input,'in.txt');Reset(Input);
  readln(n);
  SetLength(a,n,n);
  SetLength(t,n,n);
  for i:=0 to n-1 do
  for j:=0 to n-1 do
  begin
    if i=j then a[i,j]:=0 else a[i,j]:=65535;
  end;
  while not eof do
  begin
    read(t1,t2);
    dec(t1);dec(t2);
    readln(a[t1,t2]);
    a[t2,t1]:=a[t1,t2]
  end;
  for i:=0 to n-1 do
  for j:=0 to n-1 do
  begin
    if j=0 then t[i,j]:=a[0,i] else t[i,j]:=65535
  end;
  for j:=1 to n-1 do
  for i:=1 to n-1 do
  for k:=1 to n-1 do
  if i<>k then
  if (t[k,j-1]<65535)and(a[k,i]<65535) then
  if t[k,j-1]+a[k,i]<t[i,j] then
  begin
    t[i,j]:=t[k,j-1]+a[k,i];
  end;
  for i:=1 to n-1 do
  begin
    min:=0;
    for j:=1 to n-1 do
    if t[i,j]<t[i,min] then min:=j;
    write(t[i,min],' ');
  end;
  Close(Input)
end.