#!/usr/bin/env ruby
class Node
  attr_accessor :id, :edges, :cost, :fixed

  def initialize(id, edges = [], cost = nil, fixed = false)
    @id, @edges, @cost, @fixed = id, edges, cost, fixed
  end

  def show
    puts "Node (#{@id}) COST: #{cost}"
    @edges.each do |edge|
      puts "->#{edge[0]} cost:#{edge[1]}"
    end
  end

  def search
    @edges.each do |edge|

    end
  end
end

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

nodes = []
v.times do |i|
  nodes << Node.new(i)
end
nodes[r].cost = 0

e.times do
  s, t, d = gets.split.map(&:to_i)
  nodes[s].edges << [t, d]
end

processing = true
while processing
  processing = false
  nodes.each do |node|
    next if node.cost.nil? || node.fixed

    processing = true
    node.edges.each do |edge|
      cost = node.cost + edge[1]
      nodes[edge[0]].cost = cost if nodes[edge[0]].cost.nil? || nodes[edge[0]].cost > cost
    end
    node.fixed = true
  end
end

v.times do |i|
  puts nodes[i].cost || 'INF'
end