{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE BangPatterns #-}

import           Control.Applicative
import qualified Data.ByteString.Char8       as B
import qualified Data.ByteString.Unsafe      as B
import           Data.Char
import           Data.Function
import qualified Data.Vector                 as V
import qualified Data.Vector.Unboxed         as U
import qualified Data.Vector.Unboxed.Mutable as UM

main :: IO ()
main = do
    [v, e, r] <- map read.words <$> getLine
    edges <- U.unfoldrN e (readInt3.B.dropWhile isSpace) <$> B.getContents
    putStr.unlines.map showCost.U.toList.solve r $ fromEdges v edges

solve :: Vertex -> Graph -> U.Vector Cost
solve root gr = dijkstra root gr

showCost :: Cost -> String
showCost cost
    | cost < inf = show cost
    | otherwise = "INF"

-------------------------------------------------------------------------------

readInt3 :: B.ByteString -> Maybe ((Int,Int,Int), B.ByteString)
readInt3 bs = Just ((x,y,z),bsz)
  where
    Just (x, bsx) = B.readInt bs
    Just (y, bsy) = B.readInt $ B.unsafeTail bsx
    Just (z, bsz) = B.readInt $ B.unsafeTail bsy

type Vertex = Int
type Cost = Int
type Edge = (Vertex, Vertex, Cost)
type Graph = V.Vector (U.Vector (Vertex, Cost))

fromEdges :: Int -> U.Vector Edge -> Graph
fromEdges numV edges = V.map U.fromList
    . V.unsafeAccumulate (flip (:)) (V.replicate numV [])
    . U.convert
    . U.map (\(src, dst, cost) -> (src, (dst, cost)))
    $ edges

inf :: Cost
inf = 0x3f3f3f3f

dijkstra :: Vertex -> Graph -> U.Vector Cost
dijkstra root gr = U.create $ do
    dist <- UM.replicate (V.length gr) inf
    UM.unsafeWrite dist root 0
    flip fix (singleton (0, root)) $ \loop !heap ->
        case deleteFindMin heap of
            Just ((!d, !v), heap') -> do
                dv <- UM.unsafeRead dist v
                if d > dv
                then loop heap'
                else do
                    let step h (!nv, !v2nv) = do
                        let !dnv = dv + v2nv
                        old <- UM.unsafeRead dist nv
                        if dnv < old
                        then do
                            UM.unsafeWrite dist nv dnv
                            return $ insert (dnv, nv) h
                        else return h
                    U.foldM' step heap' (V.unsafeIndex gr v) >>= loop
            Nothing -> return dist

data Heap a = Fork !a [Heap a] | Empty

singleton :: a -> Heap a
singleton x = Fork x []
{-# INLINE singleton #-}

isEmpty :: Heap a -> Bool
isEmpty Empty = True
isEmpty _ = False
{-# INLINE isEmpty #-}

insert :: Ord a => a -> Heap a -> Heap a
insert x = merge (Fork x [])
{-# INLINE insert #-}

minElem :: Heap a -> Maybe a
minElem (Fork x _) = Just x
minElem _ = Nothing
{-# INLINE minElem #-}

deleteMin :: Ord a => Heap a -> Maybe (Heap a)
deleteMin (Fork _ hs) = Just $! mergePairs hs
deleteMin _ = Nothing
{-# INLINE deleteMin #-}

deleteFindMin :: Ord a => Heap a -> Maybe (a, Heap a)
deleteFindMin (Fork x hs) = case mergePairs hs of h -> Just (x, h)
deleteFindMin _ = Nothing
{-# INLINE deleteFindMin #-}

merge :: Ord a => Heap a -> Heap a -> Heap a
merge hx@(Fork x hxs) hy@(Fork y hys)
  | x <= y    = Fork x (hy:hxs)
  | otherwise = Fork y (hx:hys)
merge Empty hy = hy
merge hx _ = hx
{-# INLINE merge #-}

mergePairs :: Ord a => [Heap a] -> Heap a
mergePairs (x:y:hs) = merge (merge x y) (mergePairs hs)
mergePairs [x]      = x
mergePairs []       = Empty
{-# INLINE mergePairs #-}

Measured memory_bytes: 140504