class SimpleDirectedGraph
  def initialize(v = 0)
    @g = v.times.map{ [Float::INFINITY] * v }
  end
  
  def add_edge(v1, v2, w)
    @g[v1][v2] = w
    return @g
  end
  
  def dijkstra(r)
    # initialize
    v_num = @g.length
    dist, visited = [Float::INFINITY] * v_num, [false] * v_num
    dist[r] = 0
    
    loop do
      v = nil
      
      v_num.times do |u|
        v = u if(!visited[u] && (!v || dist[u] < dist[v]))
      end
    
      break unless v
      
      visited[v] = true
      
      v_num.times do |u|
        dist[u] = [dist[u], dist[v] + @g[v][u]].min
      end
    end
    
    return dist
  end
end

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

e.times do
  s, t, d = gets.split.map(&:to_i)
  graph.add_edge(s, t, d)
end

graph.dijkstra(r).each do |i|
  puts i == Float::INFINITY ? "INF" : i
end