class Dijkstra
  #????????????????????°???????????????????????????????????????????????????
  def initialize graph
    @graph = graph
    #?¢?????????????
    @confirms = {}
    @edges = {}
  end

  def exec start
    @edges[start] = 0
    until @edges.empty?
      edge = @edges.min
      confirm_node(edge[0])
    end
    return @confirms
  end

  def confirm_node node
    @confirms[node] = @edges[node]
    @edges.delete(node)
    @graph[node].each do |(to, length)|
      next if @confirms.key?(to)
      candidate = @confirms[node] + length
      if !@edges[to] || @edges[to] > candidate
        @edges[to] = candidate
      end
    end
  end
end

nodes,edges,start = gets.split(" ").map(&:to_i)
graph = Hash.new{|h,k|h[k] = []}
edges.times do
  s,t,d = gets.split(" ").map(&:to_i)
  graph[s] << [t,d]
end
dijkstra = Dijkstra.new(graph)
confirms = dijkstra.exec(start)
nodes.times do |i|
  puts confirms[i] ? confirms[i] : "INF"
end