{bellman ford}
const inf=maxlongint div 2;

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

var u:array[1..250002] of muchie;
    d: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
    begin
    readln(u[i].x,u[i].y,u[i].c);
    if u[i].x=1 then d[u[i].y]:=u[i].c;
    end;
close(input);
end;

procedure bellman;
var i:longint;
    ok:boolean;
begin

for i:=1 to n do d[i]:=inf;

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

while ok  do
begin
  ok:=false;
  for i:=1 to m do
      if d[u[i].y]>d[u[i].x]+u[i].c then
         begin
         d[u[i].y]:=d[u[i].x]+u[i].c;
         ok:=true;
         end;
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.