import Data.Array
import Control.Applicative
import Control.Monad
import Data.List

type Edge = (Int, Int)
type Graph = Array Int [Edge]


main :: IO ()
main = do
  [n, m, s] <- map read . words <$> getLine :: IO [Int]
  ns <- replicateM m $ do
    [s, e, c] <- map read . words <$> getLine :: IO [Int]
    return (s, [(e, c)])
  let graph = makeGraph n ns
  --mapM_ print $ indices graph
  mapM_ (putStrLn . (\ i -> if i < 0
                            then "INF"
                            else show i)) $ solve graph s

makeGraph :: Int -> [(Int, [Edge])] -> Graph
makeGraph n ns = accumArray (++) [] (0, n-1) ns

solve :: Graph -> Int -> [Int]
solve graph start = map (go start 0 []) (indices graph)
  where
    go :: Int -> Int -> [Int] -> Int -> Int
    go current cost path end
      | current == end = cost
      | all (`elem` path) (map fst nexts) = -1
      | otherwise =
          let n = head nexts in
          go (fst n) (cost + snd n) (fst n : path) end
      where
        nexts = sortBy (\a b -> compare (snd a) (snd b)) $
                graph ! current