{algoritmu bellman ford}

const inf=maxlongint div 2;

type ref=^nod;
     nod=record
         vf,c:word;
         urm:ref;
         end;

var prim:array[1..50001] of ref;
    d:array[1..50001] of longint;
    n,m:longint;

procedure adaug(x,y,cost:longint);
var c:ref;
begin
new(c);
c^.vf:=y;
c^.c:=cost;
c^.urm:=prim[x];
prim[x]:=c;
end;

procedure citire;
var i,x,y,cost:longint;
begin
assign(input,'dijkstra.in'); reset(input);
readln(n,m);
for i:=1 to m do
    begin
    readln(x,y,cost);
    adaug(x,y,cost);
    end;
close(input);
end;

procedure bellman;
var v,primu,ultimu,i:longint;
    p:ref;
    ok:boolean;
    in_coada:array[1..50001] of boolean;
    cate_ori:array[1..50001] of word;
    coada:array[1..5000000] of word;
begin
for i:=1 to n do
    begin
    d[i]:=inf;
    in_coada[i]:=false;
    coada[i]:=0;
    cate_ori[i]:=0;
    end;

d[1]:=0;
coada[1]:=1;
in_coada[1]:=true;
primu:=1;
ultimu:=1;

while primu<=ultimu do
      begin

      v:=coada[primu];
      in_coada[v]:=false;
      inc(cate_ori[v]);
      if cate_ori[v]=n+1 then break;

      p:=prim[v];

      while p<>nil do
            begin
            if d[p^.vf]>d[v]+p^.c then
               begin
               d[p^.vf]:=d[v]+p^.c;
             //  ok:=true;
               end;

            if not in_coada[p^.vf] then
               begin
               in_coada[p^.vf]:=true;
               inc(ultimu);
               coada[ultimu]:=p^.vf;
               end;
            p:=p^.urm;
            end;

      inc(primu);
      end;
end;

procedure afisare;
var i:longint;
begin
assign(output,'dijkstra.out'); rewrite(output);
for i:=2 to n do
    if d[i]=inf then write(0,' ')
                else write(d[i],' ');
close(output);
end;

begin
citire;
bellman;
afisare;
end.