program dijkstra;
type info=record
        x:word;
        y:word;
        l:integer;
        end;
var a:array[1..250000] of info;
    d:array[1..50000] of longint;
    n,m,i:longint;
    ok:boolean;
    b:array[1..1 shl 17] of char;
begin
assign(input,'dijkstra.in');settextbuf(input,b); reset(input);
assign(output,'dijkstra.out'); rewrite(output);
readln(n,m);
for i:=1 to m do readln(a[i].x,a[i].y,a[i].l);
close(input);
for i:=1 to n do d[i]:=-1;
d[1]:=0;ok:=true;
while ok do begin
            ok:=false;
            for i:=1 to m do
                if (d[a[i].x]<>-1)and((d[a[i].y]=-1)or(d[a[i].y]>d[a[i].x]+a[i].l)) then
                        begin
                        d[a[i].y]:=d[a[i].x]+a[i].l;
                        ok:=true;
                        end;
            end;
for i:=2 to n do
        if d[i]=-1 then write('0 ')
                   else write(d[i],' ');
close(output);
end.