class Node
  attr_accessor :name, :child, :done, :cost
  def initialize(i)
    @name = i
    @child = {}
    @done = false
    @cost = 1.0 / 0.0
  end
  def >(other)
    return self.cost < other.cost ? true : false
  end
  def <(other)
    return self.cost > other.cost ? false : true
  end
end

class Graph
  attr_accessor :node
  def initialize(v)
    @node = Array.new(v){|i| Node.new(i)}
  end
  def print
    @node.size.times{|i|
      if @node[i].cost < 1.0 / 0.0
        puts @node[i].cost
      else
        puts "INF"
      end
    }
  end
end

class Heep
  def initialize
    @node = []
  end
  def insert(num)
    i = @node.size
    @node[i] = num
    p = (i+1)/2-1
    while i > 0 && @node[p] < @node[i]
      @node[i], @node[p] = @node[p], @node[i]
      i = p
      p = (i+1)/2-1
    end
  end
  def extract
    ret = @node[0]
    if @node.size > 1
      @node[0] = @node.pop()
      maxHeapify(0)
    else
      @node = []
    end
    return ret
  end
  def maxHeapify(i)
    h = @node.size
    largest = i
    l = 2 * i + 1
    largest = l if l < h && @node[l] > @node[largest]
    r = 2 * i + 2
    largest = r if r < h && @node[r] > @node[largest]
    if largest != i then
      @node[i], @node[largest] = @node[largest], @node[i]
      maxHeapify(largest)
    end
  end
  def size
    return @node.size
  end
  def contain(node)
    if @node.index(node) == nil
      return false
    else
      return true
    end
  end
end

v, e, r = gets.split.map(&:to_i)

graph = Graph.new(v)

e.times{
  s, t, d = gets.split.map(&:to_i)
  graph.node[s].child[t] = d
}

q = Heep.new
graph.node[r].cost = 0
q.insert(graph.node[r])

loop do
  break if q.size == 0
  doneNode = q.extract
  doneNode.done = true
  doneNode.child.each{|t,d|
    cost = doneNode.cost + d
    if cost < graph.node[t].cost then
      graph.node[t].cost = cost
      q.insert(graph.node[t])
    end
  }
end

graph.print