program mincammino;
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;
    dist, S,E,P : array[0..MAX-1] of int64;
    q1, q2 : array[0..QSIZE-1] of int64;

 
procedure bfs(partenza : int64;arrivo:int64; var res : array of int64); 
 var qhead, qcount, first, second, i, j : int64;
   
 begin
   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<res[first] then res[first]:=second
                                                            else continue;
                                    end;                                           
         visited[first] := True;
         res[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;
 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]);
  for h:=0 to N-1 do
   begin
     setlength(graph[h], 1); 
     setlength(peso[h], 1);
     gsize[h] := 0;
     gcapa[h] := 1;
     dist[h] := maxlongint;
  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;
    bfs(0,N-1,dist);
  for i:= 0 to N-1 do  begin if dist[i]=maxlongint then dist[i]:=-1;
                                                     write(dist[i],' '); end;
                                                   
end.