const tfi='bellmanford.in';
      tfo='bellmanford.out';
      maxn=50500;
      maxm=250250;
type  ds=record
          u,v,x:longint;
        end;
var   fi,fo:text;
      last,first,n,m:longint;
      li:array[0..maxm] of ds;
      f,q:array[0..maxn] of longint;
      inq:array[0..maxn] of boolean;
      ke,st,c:array[0..maxm] of longint;

procedure enter;
var i:longint;
begin
  read(fi,n,m);
  for i:=1 to m do
   with li[i] do
   begin
     read(fi,u,v,x);
     inc(st[u]);
   end;

  inc(st[1]);
  for i:=2 to n+1 do st[i]:=st[i]+st[i-1];

  for i:=1 to m do
   with li[i] do
    begin
     dec(st[u]);
     ke[st[u]]:=v;
     c[st[u]]:=x;
    end;
end;

procedure push(u:longint);
begin
  if inq[u] then exit;
  inc(last);
  if last>maxn then last:=1;
  inq[u]:=true;
  q[last]:=u;
end;

function pop:longint;
begin
  inc(first);
  if first>maxn then first:=1;
  pop:=q[first];
  inq[pop]:=false;
end;

procedure process;
var i,j:longint;
begin
  fillchar(inq,sizeof(inq),false);
  fillchar(f,sizeof(f),127);
  f[1]:=0;
  last:=0; first:=0;
  push(1);
  repeat
    i:=pop;
    for j:=st[i] to st[i+1]-1 do
     if f[ke[j]]>f[i]+c[j] then
      begin
       f[ke[j]]:=f[i]+c[j];
       push(ke[j]);
      end;
  until last=first;
end;

procedure print;
var i:longint;
begin
  for i:=2 to n do write(fo,f[i],' ');
end;

begin
  assign(fi,tfi); reset(fi);
  assign(fo,tfo); rewrite(Fo);
  enter;
  process;
  print;
  close(fi); close(fo);
end.