program micammino;
const MAX = 200000;
      QSIZE = 400000;
var N, M,a,b,c,h,i: int64;
    graph : array[0..MAX-1] of array of int64;
    peso : array[0..MAX-1] of array of int64;
    gsize, gcapa: array[0..MAX-1] of int64;
    visited : array[0..MAX-1] of boolean;
    D, S,E,P : array[0..MAX-1] of int64;
    q1, q2 : array[0..QSIZE-1] of int64;

 
procedure mincammino(partenza:int64; arrivo:int64; var D : array of int64); 
 var qhead, qcount, first, second, i, j : int64;
   
 begin
   
   for h:=0 to N-1 do
       begin
        setlength(graph[h], 1); 
        setlength(peso[h], 1);
        gsize[h] := 0;
        gcapa[h] := 1;
        D[h] := maxlongint;
      end;
      q1[0] := partenza; q2[0] := 0;
   qhead := 0; qcount := 1;
   for i:=0 to N-1 do visited[i] := False;
   while qcount > 0 do
       begin
         first := q1[qhead];
         second := q2[qhead];
         inc(qhead);
         if qhead = QSIZE then
         qhead := 0;
         dec(qcount);
         if (visited[first]=true) then
                                    begin
                                      if second<D[first] then D[first]:=second
                                                            else continue;
                                    end;                                           
         visited[first] := True;
         D[first] := second;
         for j:=0 to gsize[first]-1 do
                 begin
                  q1[(qhead + qcount) mod QSIZE] := graph[first][j];
                  q2[(qhead + qcount) mod QSIZE] := second + peso[first][j];
                  inc(qcount);
                end;
       end;
    for h:=0 to M-1 do
      begin
       a := S[h]; b := E[h]; c:=P[h];
       if gsize[a] = gcapa[a] then
            begin
              gcapa[a] := gcapa[a] shl 1;
              setlength(graph[a], gcapa[a]);
              setlength(peso[a], gcapa[a]);
            end;
       graph[a][gsize[a]] := b;
       peso[a][gsize[a]] := c;
       inc(gsize[a]);
     end;  
 end;
begin
 (*assign(input,  'input.txt');  reset(input);
  assign(output, 'output.txt'); rewrite(output);*)
  readln(N,M); 
  for h:=0 to M-1 do readln(S[h],E[h],P[h]);
  mincammino(0,N-1,D);
  for i:= 0 to N-1 do  begin if D[i]=maxlongint then D[i]:=-1;  write(D[i],' '); end;
                                                   
end.