import Control.Monad
import Control.Applicative
import qualified Data.PQueue.Min as PQ
import Data.List

data Graph = Graph {vertexs :: [Vertex], edges :: [Edge]} deriving Show
data Vertex = Vertex {number :: Int, cost :: Int} deriving Show
data Edge = Edge {start :: Int, to :: Int, weight :: Int} deriving Show

instance Eq Vertex where
    l == r = cost l == cost r

instance Ord Vertex where
    l `compare` r = cost l `compare` cost r

main :: IO ()
main = do
    (start, graph) <- parseInput
    putStrLn . unlines . map myShow $ solve start graph

myShow :: Int -> String
myShow (-1) = "INF"
myShow x = show x

parseInput :: IO (Int, Graph)
parseInput = do
    [v, e, r] <- (map read . words) <$> getLine
    edges <- parseEdges e
    return (r, newGraph v edges)

parseEdges :: Int -> IO [Edge]
parseEdges n = replicateM n parseEdge

parseEdge :: IO Edge
parseEdge = do
    [s, t, d] <- (map read . words) <$> getLine
    return Edge {start = s, to = t, weight = d}

newGraph :: Int -> [Edge] -> Graph
newGraph n_v es = Graph {vertexs = vs, edges = es} where
    vs = [Vertex {number = i, cost = -1} | i <- [0..n_v-1]]


solve :: Int -> Graph -> [Int]
solve start graph = map cost $ vertexs graph' where
    pq = PQ.singleton startV
    startV = (vertexs graph !! start) {cost = 0}
    graph' = dijkstra pq $ update graph startV

dijkstra :: PQ.MinQueue Vertex -> Graph -> Graph
dijkstra pq graph
    | PQ.null pq   = graph
    | otherwise = dijkstra pq' graph' where
          pq' = foldl' (\pq x -> PQ.insert x pq) (PQ.deleteMin pq) newVs
          graph' = foldl' update graph newVs
          newVs = filter (canUpdate graph) $ neighbors graph v
          v = PQ.findMin pq

canUpdate :: Graph -> Vertex -> Bool
canUpdate graph v = oldC > newC || oldC == -1 where
    oldC = cost $ vertexs graph !! (number v)
    newC = cost v

neighbors :: Graph -> Vertex -> [Vertex]
neighbors graph v = map (move v) es where
    es = filter (\e -> start e == number v) (edges graph)

update :: Graph -> Vertex -> Graph
update graph v = graph {vertexs = newVertexs} where
    newVertexs = take n vs ++ [v] ++ drop (n + 1) vs
    n = number v
    vs = vertexs graph

move :: Vertex -> Edge -> Vertex
move v e = Vertex {number = t, cost = c} where
    t = to e
    c = cost v + weight e