{algoritmu bellman ford}
const inf=maxlongint div 2;

type muchie=record
            x,y:longint;
            c:integer;
            end;

var u:array[1..50001] of muchie;
    d,tata:array[1..50001] of longint;
    n,m:longint;

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

procedure bellman;
var i,varf,lx,ly,cost:longint;
    ok:boolean;
begin
for i:=1 to n do
    begin
    d[i]:=inf;
    tata[i]:=0;
    end;

varf:=1;
ok:=true;
d[1]:=0;

while ok and (varf<n) do
      begin

      ok:=false;

     for i:=1 to m do
         begin
         lx:=u[i].x;
         ly:=u[i].y;
         cost:=u[i].c;

         if d[ly]>d[lx]+cost then
            begin
            d[ly]:=d[lx]+cost;
            tata[ly]:=lx;
            ok:=true;
            end;
         end;

     inc(varf);
     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.