import Control.Monad
import Control.Applicative
import Data.List
import qualified Data.Map as Map
import Data.Array
import qualified Data.ByteString.Char8 as BC
import Data.Maybe
import qualified Data.Set as Set
import qualified Data.Sequence as Sq
import qualified Data.IntMap as IMap
import Data.Sequence (ViewL(..),ViewR(..),(><),(<|),(|>),Seq)

bsreadInt :: BC.ByteString -> Int
bsreadInt = fst . fromJust . BC.readInt

--有向隣接Map 　[[1,2,7] , [3,1,5]] --> fromList [(1,fromList [(2,7)]) , (3,fromList [(1,5)])]
setadj :: [[Int]] -> IMap.IntMap (IMap.IntMap Int) -> IMap.IntMap (IMap.IntMap Int)
setadj [] adj = adj
setadj (x:xs) adj = if IMap.member a adj == True
                    then setadj xs add
                    else setadj xs (IMap.insert a (IMap.singleton b c) add)
                    where a = x !! 0
                          b = x !! 1
                          c = x !! 2
                          add = IMap.insert a addbc adj
                          addbc = IMap.insert b c ((IMap.!) adj a)

nsetadj :: [[Int]] -> IMap.IntMap (IMap.IntMap Int) -> IMap.IntMap (IMap.IntMap Int)
nsetadj xs adj = setadj (xs ++ (map ex xs)) adj
ex an = [an !! 1, an !! 0 , an !! 2]

minvaluemap :: IMap.IntMap (Int,[Int]) -> Int -> Int -> (Int,Int)
minvaluemap f k v = if IMap.null f == True
                    then (k,v)
                    else if (minv < v) || (k == -1)
                         then minvaluemap (IMap.deleteMin f) mink minv
                         else minvaluemap (IMap.deleteMin f) k v
                           where mink = head $ IMap.keys f
                                 minv = fst $ fst (fromMaybe ((-1,[]),IMap.empty) (IMap.minView f))

-- minvaluemap :: IMap.IntMap Int -> Int -> Int -> (Int,Int)
-- minvaluemap f k v = if IMap.null f == True
--                     then (k,v)
--                     else if (minv < v) || (k == -1)
--                          then minvaluemap (IMap.deleteMin f) mink minv
--                          else minvaluemap (IMap.deleteMin f) k v
--                            where mink = head $ IMap.keys f
--                                  minv = fst (fromMaybe (-1,IMap.empty) (IMap.minView f))
-- m -> n (cost c)たちに更新
--(cost,path) -> m -> (n,cost) -> (cost,path)
upd :: IMap.IntMap (Int,[Int]) -> Int -> [(Int,Int)] -> IMap.IntMap (Int,[Int])
upd g m [] = g
upd g m (x:xs) = if IMap.member n g == False
                 then upd (IMap.insert n (c,l) g) m xs
                 else if (fst ((IMap.!) g n)) > c
                      then upd (IMap.insert n (c,l) g) m xs
                      else upd g m xs
                         where n = fst x
                               c = (snd x) + fst ((IMap.!) g m)
                               l = n : (snd ((IMap.!) g m))

--確定リスト->現時点での最短コスト->隣接情報->ゴールの頂点->(cost,path)
dijkstra :: [Int] -> IMap.IntMap (Int,[Int]) -> IMap.IntMap (IMap.IntMap Int) -> Int -> (Int,[Int])
dijkstra con f adj g = if p == g
                       then (fst ((IMap.!) f g),reverse (snd((IMap.!) f g)) ) 
                       else if IMap.member p adj == False
                            then (-1,[])
                            else if (newcon == -1)
                                 then (-1,[]) -- 到達不能
                                 else dijkstra con2 f2 adj g
                                   where p = head con
                                         adjp = IMap.assocs ((IMap.!) adj p) --pから向かう頂点
                                         f2 = upd f p adjp
                                         newcon = (fst $ minvaluemap (delkeys f2 con) (-1) (-1))
                                         con2 = newcon:con

delkeys f [] = f
delkeys f (x:xs) = delkeys (IMap.delete x f) xs
sqleft :: Seq a -> a
sqleft q = sqleft_(Sq.viewl q)
sqleft_ :: ViewL a -> a
sqleft_ (x :< xs) = x
sqright :: Seq a -> a
sqright q = sqright_(Sq.viewr q)
sqright_ :: ViewR a -> a
sqright_ (xs :> x) = x

solve n m r g adj = if fst (dijkstra [r] (IMap.singleton r (0,[r])) adj g) == -1
                   then "INF"
                   else show $ fst (dijkstra [r] (IMap.singleton r (0,[r])) adj g)
main = do
    [n,m,r] <- map bsreadInt . BC.words <$> BC.getLine --n:vertex , m:edge
    ab <- map ((map bsreadInt . BC.words)) <$> replicateM m BC.getLine -- a-->b,c :path,cost のリスト
    let adj = setadj ab IMap.empty
    mapM_ putStrLn [solve n m r g adj | g<-[0..(n-1)]]


