var     a:array[1..3,1..250000]of longint;
        v:array[1..50000] of longint;
        n,m,i,j:longint;
        f,g:text;

procedure rec(p,s:longint);
var     i:longint;
begin
  if (v[a[2,p]]=0)or(v[a[2,p]]>s) then v[a[2,p]]:=s;
  for i:=1 to n do
    if a[1,i]=a[2,p] then rec(i,s+a[3,i]);
end;
begin
  assign(f,'dijkstra.in');
  assign(g,'dijkstra.out');
  reset(f);
  rewrite(g);
  readln(f,n,m);
  for i:=1 to m do
  for j:=1 to 3 do
    read(f,a[j,i]);
  for i:=1 to m do
    if a[1,i]=1 then
      rec(i,a[3,i]);
  for i:=2 to n do
    write(g,v[i],' ');
  close(g);
end.