type nd=^nod;
     nod=record
          val,lung:longint;
          next:nd
         end;
     graf=array[1..50000]of nd;
var g:graf;
    n,m,x,y,i,l:longint;
    f:text;
    p:nd;
    coada,cost:array[1..50000]of longint;

begin
assign(f,'belmanford.in');
reset(f);
readln(f,n,m);
for i:=1 to m do
 begin
  readln(f,x,y,l);
  new(p);
  p^.val:=y;
  p^.lung:=l;
  p^.next:=g[x];
  g[x]:=p
 end;
close(f);
for i:=1 to n do
 cost[i]:=1000000000;
cost[1]:=0;
x:=0;y:=1;
coada[y]:=1;
repeat
inc(x);
p:=g[coada[x]];
while p<>nil do
 begin
  if cost[coada[x]]+p^.lung<cost[p^.val] then
   begin
    inc(y);
    coada[y]:=p^.val;
    cost[coada[y]]:=cost[coada[x]]+p^.lung;
   end;
  p:=p^.next;
 end;
until x=y;
assign(f,'belmanford.out');
rewrite(f);
for i:=2 to n do
 if cost[i]<>1000000000 then write(f,cost[i],' ')
                        else write(f,'0 ');
close(f);
end.