//Dijkstra doar lungimile drumurilor de cost minim
//un singur varf de plecare -> start ; drumuri catre celelalte n-1 noduri
//O(n*m) 100p infoarena
//max 204 ms //n<=50 000 m<=250 000
program dijkkk;
const infinit=1000000001;
type muchie=record
     x,y,cost:longint;
     end;
     vect=array[1..50001]of longint;
     vector_muchii=array[1..250001]of muchie;
var a:vector_muchii; d:vect;
    n,m:longint;
    f,g:text;
    intrare,iesire:array[1..300000]of char;

procedure initializare;
var i:longint;
begin
readln(f,n,m);
for i:=1 to m do readln(f,a[i].x,a[i].y,a[i].cost);
for i:=1 to n do d[i]:=infinit;
end;

procedure dijk;
var i:longint;ok:boolean;
begin
d[1]:=0;
ok:=true;
while ok do
  begin
  ok:=false;
  for i:=1 to m do
    if d[a[i].y]>d[a[i].x]+a[i].cost then begin
                                          ok:=true;
                                          d[a[i].y]:=d[a[i].x]+a[i].cost;
                                          end;
  end;
end;

procedure afisare;
var i:longint;
begin
for i:=2 to n do
  if d[i]=infinit then write(g,'0 ')
                  else write(g,d[i],' ');
end;

begin
assign(f,'dijkstra.in');  reset(f);   settextbuf(f,intrare);
assign(g,'dijkstra.out'); rewrite(g); settextbuf(g,iesire);
initializare;
dijk;
afisare;
close(f);close(g);
end.