class PQueue

  VERSION = "2.0.0"  #:erb: VERSION = "<%= version %>"

  def initialize(elements=nil, &block) # :yields: a, b
    @que = []
    @cmp = block
    replace(elements) if elements
  end

 protected

  attr_reader :que #:nodoc:

 public

  attr_reader :cmp

  def pop
    return nil if empty?
    @que.pop
  end

  def empty?
    @que.empty?
  end

  def clear
    @que.clear
    self
  end

  def to_a
    @que.dup
  end

  def replace(elements)
    if elements.kind_of?(PQueue)
      initialize_copy(elements)
    else
      @que.replace(elements.to_a)
      sort!
    end
    self
  end

 private

  def initialize_copy(other)
    @cmp  = other.cmp
    @que  = other.que.dup
    sort!
  end

  def reheap(k)
    return self if size <= 1

    que = @que.dup

    v = que.delete_at(k)
    i = binary_index(que, v)

    que.insert(i, v)

    @que = que

    return self
  end

  def sort!
    @que.sort! do |a,b|
      case @cmp.call(a,b)
      when  0, nil   then  0
      when  1, true  then  1
      when -1, false then -1
      else
        warn "bad comparison procedure in #{self.inspect}"
        0
      end
    end
    self
  end

end # class PQueue

## Aizu Online Judge Problem starts here.

# 無限大の距離に利用する.
INF = 2**25

def min(x, y)
  x < y ? x : y
end

# 重み付き隣接行列に変換する.
# edgeがない場合は-1が入っている.
def toAdj(edges, n)
  a = Array.new(n).map{ Array.new(n, -1) }
  edges.each do |i, j, c|
    a[i][j] = c
  end
  a
end

# Bellman-Ford法.
# dsにsからの距離を格納して返す.
# 到達不可能の場合、INFが入っている.
# 最初、重みが正の数だと思っていたので、途中で失敗した.
# AizuOnlineJudgeでは19.93秒かかり、Time Limit Exceededとなった.
def bellmanFord(adj, n, m, s)
  ds = Array.new(n, INF)
  ds[s] = 0

  n.times do # 頂点の個数だけループする.
    adj.each_with_index do |row, i|
      row.each_with_index do |c, j|
        ds[j] = min(ds[j], ds[i] + c) if c >= 0 # 重みは0以上
      end
    end
  end

  ds
end

# Dijkstra法
def dijkstra(adj, n, m, s)
  ds = Array.new(n, INF)
  ds[s] = 0

  unsolvedVs = Array.new(n)
  n.times do |i|
    unsolvedVs[i] = i
  end

  unsolvedQueue = PQueue.new(unsolvedVs){ |x, y| x < y ? 0 : 1 } # Minimum proirity queue.

  until unsolvedQueue.empty?
    u = unsolvedQueue.pop

    unsolvedQueue.to_a.each do |j|
      adj.each_with_index do |row, i|
        ds[j] = min(ds[j], ds[i] + row[j]) if row[j] >= 0
      end
    end
  end

  ds
end

if __FILE__ == $0
  n, m, r = gets.split.map(&:to_i)

  edges = m.times.map{ gets.split.map(&:to_i) }
  adjMatrix = toAdj(edges, n)

#  bellmanFord(adjMatrix, n, m, r).each do |c|
#    puts c == INF ? "INF" : c.to_s
#  end

  dijkstra(adjMatrix, n, m, r).each do |c|
    puts c == INF ? "INF" : c.to_s
  end
end