var     a:array[1..3,1..250000]of longint;
        b:array[1..50000] of longint;
        n,m,i,j:longint;
        bb:boolean;
        f,g:text;

{procedure rec(p,s:longint);
var     i:longint;
begin
  if (v[a[2,p]]=0)or(v[a[2,p]]>s) then v[a[2,p]]:=s;
  for i:=1 to m do
    if a[1,i]=a[2,p] then rec(i,s+a[3,i]);
end;}
begin
  assign(f,'dijkstra.in');
  assign(g,'dijkstra.out');
  reset(f);
  rewrite(g);
  readln(f,n,m);
  for i:=1 to m do
  for j:=1 to 3 do
    read(f,a[j,i]);
 { for i:=1 to m do
    if a[1,i]=1 then
      rec(i,a[3,i]);}

  for i:=1 to n do
    b[i]:=-1;
  b[1]:=0;
  bb:=true;
  while bb do
    begin
      bb:=false;
      for i:=1 to m do
        if (b[a[1,i]]<>-1)and((b[a[2,i]]=-1)or(b[a[2,i]]>b[a[1,i]]+a[3,i]))
          then
            begin
              b[a[2,i]]:=b[a[1,i]]+a[3,i];
              bb:=true;
            end;
    end;

  for i:=2 to n do
    if b[i]<>-1 then
    write(g,b[i],' ') else write(g,0,' ');
  close(g);
end.