type matrice=array[1..50000,1..50000] of integer;

const inf=2147483647;

var n,i,j,min,m,v,a,b,c:longint;
 
    f:text;
    d:matrice;
    nume1,nume2:string;
    p,x,t:array[1..50000] of integer;

procedure citeste;
begin
     nume1:='dijkstra.in';nume2:='dijkstra.out';
     assign(f,nume1);reset(f);
     readln(f,n,m);
     for i:=1 to m do begin
         readln(f,a,b,c);
         d[a,b]:=c;
     end;
     readln(f,v);
     close(f);
end;
procedure dijkstra;
begin
     for i:=1 to n do x[i]:=inf;
     x[v]:=0;
     for i:=1 to n do begin
         min:=inf;
         for j:=1 to n do
             if (x[j]<min) and (p[j]=0) then begin
                a:=j;min:=x[j];
             end;
         p[a]:=1;
         for j:=1 to n do
             if (d[a,j]>0) and (d[a,j]+x[a]<x[j]) then begin
                x[j]:=d[a,j]+x[a];t[j]:=a;
             end;
     end;

end;

begin
     citeste;
     assign(f,nume2);rewrite(f);
     dijkstra;
     for i:=2 to n do
            write(f,x[i],' ');
     close(f);
end.