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

# 重み付き隣接行列に変換する.
# 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が入っている.
# 最初、重みが正の数だと思っていたので、途中で失敗した.
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|
        if c >= 0 # 重みは0以上
          ds[j] = ds[j] < ds[i] + c ? ds[j] : ds[i] + c
        end
      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
end