type ref=^nod;
nod=record
    nod,cost:word;
    adr:ref;
    end;
const inf=50000005;
var poz,heap:array[1..50000] of word;
d:array[1..50000] of longint;
v:array[1..50000] of ref;
u:ref;
n,m,i,a,b,c,x,aux:longint;
f,g:text;
s:string;
procedure citire(var a1,b1,c1:longint);
          var cnt:longint;
          begin
          cnt:=1;
          a1:=0;b1:=0;c1:=0;
          while (s[cnt]>='0') and (s[cnt]<='9') do
                begin
                a1:=a1*10+ord(s[cnt])-48;
                inc(cnt);
                end;
          inc(cnt);
          while (s[cnt]>='0') and (s[cnt]<='9') do
                begin
                b1:=b1*10+ord(s[cnt])-48;
                inc(cnt);
                end;
          inc(cnt);
          while (cnt<=length(s)) and (s[cnt]>='0') and (s[cnt]<='9') do
                begin
                c1:=c1*10+ord(s[cnt])-48;
                inc(cnt);
                end;
          end;
procedure perc(p:word);
          begin
          while (p>1) and (d[heap[p shr 1]]>d[heap[p]]) do
                begin
                aux:=heap[p];
                heap[p]:=heap[p shr 1];
                heap[p shr 1]:=aux;
                poz[heap[p]]:=p;
                poz[heap[p shr 1]]:=p shr 1;
                p:=p shr 1;
                end;
          end;
procedure sift(p:word);
          var min:longint;
          begin
          while (p<=x shr 1) and ((d[heap[p]]>d[heap[p*2]]) or (d[heap[p]]>d[heap[p*2+1]])) do
                begin
                if d[heap[p*2]]<d[heap[p*2+1]] then
                   min:=p*2
                else
                    min:=p*2+1;
                aux:=heap[p];
                heap[p]:=heap[min];
                heap[min]:=aux;
                poz[heap[p]]:=p;
                poz[heap[min]]:=min;
                p:=min;
                end;
          end;
begin
assign(f,'dijkstra.in');
assign(g,'dijkstra.out');
reset(f);rewrite(g);
readln(f,s);
citire(n,m,a);
for i:=1 to m do
    begin
    readln(f,s);
    citire(a,b,c);
    if v[a]=nil then
       begin
       new(v[a]);
       v[a]^.nod:=b;
       v[a]^.cost:=c;
       v[a]^.adr:=nil;
       end
    else
        begin
        new(u);
        u^.nod:=b;
        u^.cost:=c;
        u^.adr:=v[a];
        v[a]:=u;
        end;
    end;
for i:=2 to n do
    d[i]:=inf;
poz[1]:=1;
x:=1;
heap[1]:=1;
while x>0 do
      begin
      a:=heap[1];
      poz[heap[1]]:=0;
      if a<>1 then
         begin
         heap[1]:=heap[x];
         poz[heap[1]]:=1;
         end;
      dec(x);
      sift(1);
      u:=v[a];
      while u<>nil do
            begin
            if d[u^.nod]>d[a]+u^.cost then
               begin
               d[u^.nod]:=d[a]+u^.cost;
               if poz[u^.nod]>0 then
                  if (poz[u^.nod]>1) and (d[heap[poz[u^.nod] shr 1]]>d[heap[poz[u^.nod]]]) then
                     perc(poz[u^.nod])
                  else
                      sift(poz[u^.nod])
               else
                   begin
                   inc(x);
                   heap[x]:=u^.nod;
                   poz[u^.nod]:=x;
                   perc(x);
                   end;
               end;
            u:=u^.adr;
            end;
      end;
for i:=2 to n do
    if d[i]=inf then
       write(g,'0 ')
    else
        write(g,d[i],' ');
close(f);close(g);
end.