uses crt;
  type vektor=array[1..150] of integer;
       matrix=array[1..150,1..150] of integer;
   var benne:boolean;
     a,b,c,kcs,min:integer;
      f,g:text;
      x:matrix;
      v,jart,os:vektor;
      n,m,i,j,csucs:longint;
   begin
   clrscr;
  assign(f,'dijkstra.in');
reset(f);
readln(f,n,m,kcs);
for i:= 1 to m do
 begin
  readln(f,a,b,c);
  x[a,b]:=c;
 end;
close(f);
for i:= 1 to n do
 os[i]:=0;
for i:= 1 to n do
 for j:= 1 to n do
  if (x[i,j]=0) and (i<>j)
   then
    x[i,j]:=10000;
for i:= 1 to n do
 v[i]:=x[kcs,i];
for i:= 1 to n do
 jart[i]:=0;
jart[kcs]:=1;
for i:= 1 to n do
 os[i]:=4;
repeat
benne:=false;
for i:= 1 to n do
 if jart[i]=0
  then
   benne:=true;
 if benne
  then
  begin
  min:=maxint;
  for i:=1 to n do
   begin
    if (v[i]<min) and (jart[i]=0)
     then
      begin
      min:=v[i];
      csucs:=i;
      end;
   end;
   jart[csucs]:=1;
    for i:= 1 to n do
     begin
      if ((x[csucs,i]+min) <v[i]) and (jart[i]=0)
       then
        begin
        v[i]:=x[csucs,i]+min;
        os[i]:=csucs;
        end;
     end;
  end;
until not benne;
assign(g,'dijkstra.out');
rewrite(g);
for i:= 1 to n do
 write(g,v[i],' ');
close(g);
end.