Dijkstra

type
  vertix = record
    v, w: Integer;
  end;

var
  g: array of array of vertix;
  d: array of Integer;
  vis: array of Boolean;
  N, M, S, i, v, u, w, j: Integer;

procedure AddElem(v, u, w: Integer);
begin
  SetLength(g[v], Length(g[v]) + 1);
  g[v, high(g[v])].v := u;
  g[v, high(g[v])].w := w;
end;

begin
  Assign(input, 'input.txt'); Reset(input);
  Assign(output, 'output.txt'); Rewrite(output);
  Readln(N, M, S);
  SetLength(d, N);
  SetLength(vis, N);
  for i := 0 to N - 1 do
    d[i] := high(Integer);
  d[S - 1] := 0;
  SetLength(g, n);
  for i := 0 to M - 1 do begin
    Readln(v, u, w);
    AddElem(v - 1, u - 1, w);
  end;
  for i := 0 to N - 1 do begin
    v := -1;
    for j := 0 to N - 1 do
      if (not vis[j]) and ((v = -1) or (d[j] < d[v])) then
        v := j;
    if d[v] = high(Integer) then break;
    vis[v] := true;
    for j := 0 to Length(g[v]) - 1 do begin
      u := g[v, j].v;
      w := g[v, j].w;
      if (d[v] + w) < d[u] then
        d[u] := d[v] + w;
    end;
  end;
  for i := 0 to N - 1 do
    if d[i] = high(Integer) then
      write('-1 ')
    else
      write(d[i], ' ');
  Close(input); Close(output);
end.