import Control.Applicative
import Control.Monad
import qualified Data.ByteString.Char8 as BS
import qualified Data.List as L
import Data.Map ((!))
import qualified Data.Map as M
import Data.Maybe
import qualified Data.Set as S
import qualified Data.Tuple as T

addToSet set xs = L.foldl' (\ acc x -> S.insert (T.swap x) acc) set xs

addToMap m xs = L.foldl' (\ acc (x, d) -> M.insert x d acc) m xs

dijkstra graph source = dijkstra' graph (S.singleton (0, source))
                        (M.singleton source 0)

dijkstra' graph pq res
    | S.null pq = res
    | otherwise = dijkstra' graph (addToSet pq' info) (addToMap res info)
    where
      fwd = M.findWithDefault
      ((dis, node), pq') = S.deleteFindMin pq
      nodes = fwd [] node graph
      update = filter (\ (x, e) -> M.notMember x res ||
                                   dis + e < res!x) nodes
      info = map (\ (x, e) -> (x, dis + e)) update

buildGraph edges =
    let g = L.groupBy (\ (x, _, _) (y, _, _) -> x == y) edges
    in M.fromList (map (\ x -> (f1 $ head x, map (\ (_, y, z) -> (y, z)) x)) g)

readInt' = fst . fromJust . BS.readInt

f1 (x, _, _) = x

f3 (_, _, x) = x

main = do
  contents <- BS.lines <$> BS.getContents
  let edges = map (\ [x, y, z] -> (x, y, z))
              (map (\ x -> map readInt' (BS.words x)) contents)
      res = dijkstra (buildGraph $ L.sort $ tail edges) (f3 $ head edges)
      n = f1 $ head edges
  forM_ [0..(n - 1)] $ \i -> do
         if M.member i res
         then print (M.findWithDefault (-1) i res)
         else putStrLn "INF"