program cost_minim;
const pinf=32760;
r=1;
var f:text;
s,t:array[1..100] of shortint;
d:array[1..100] of integer;
v:array[1..100,1..100]of integer;
i,j,l,c,q,min,poz:integer;
n,m:longint;

begin
assign(f,'dijkstra.in');
reset(f);
readln(f,n,m);
for i:=1 to n do
  for j:=1 to n do
    if i=j then
      v[i,j]:=0
    else
      v[i,j]:=pinf;
for i:=1 to m do
  begin
  readln(f,l,c,q);
  v[l,c]:=q
  end;
close(f);

for i:=1 to n do
  begin
  s[i]:=0;
  t[i]:=0
  end;
s[r]:=1;

for i:=1 to n do
  begin
  d[i]:=v[r,i];
  if i<>r then
    if d[i]<pinf then
      t[i]:=r
  end;

for i:=1 to n-1 do
  begin
  min:=pinf;
  poz:=-1;
  for j:=1 to n do
    if s[j]=0 then
      if d[j]<min then
        begin
        min:=d[j];
        poz:=j
        end;
  if poz<>-1 then
    begin
    s[poz]:=1;
    for j:=1 to n do
      if s[j]=0 then
        if d[j]>d[poz]+v[poz,j] then
          begin
          d[j]:=d[poz]+v[poz,j];
          t[j]:=poz
          end
    end
  end;

assign(f,'dijkstra.out');
rewrite(f);
for i:=1 to n do
  if i<>r then
    if t[i]<>0 then
      begin
      write(f,d[i],' ');
      writeln
      end
    else
      write(f,'0 ');
close(f)
end.