{-# LANGUAGE ViewPatterns #-}
import Control.Arrow
import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as B
import Data.Ord
import qualified Data.IntMap.Strict as M

main :: IO ()
main = readLine >>= main'
    where
        main' [n, m] = readContents (n + m - 1) >>= printRes . solve n
        printRes = mapM_ print 

solve ::Int -> [[Int]] -> [Int]
solve n = map snd . sortBy (comparing fst) . check 0 . build
    where
        build es = (g, sh)
            where
                g = M.fromDistinctAscList $ zipWith zf ins cs
                sh = push (Edge 0 0 0 . fst $ minimumBy (comparing snd) ins) empty 
                zf (i, c) (_, p) = (i, Node c p)
                ins = M.toAscList $ foldl' ff0 (acc0 0) es
                cs = M.toAscList $ foldl' ff1 (acc0 []) es
                acc0 = M.fromDistinctAscList . zip [1..n] . repeat 
                ff0 acc [a, b] = M.update (return . succ) b acc
                ff1 acc [a, b] = M.update (return . (b :)) a acc

        check c (g, pop -> Just (Edge w x y z, xs))
            | c == n = []
            | otherwise = (z, y) : check (c + 1) (g, ys)
            where
                ys = foldl' ff xs . children $ g M.! z
                ff acc i = push (Edge (w + 1) (pc $ g M.! i) z i) acc 
        check _ _ = []

data Node = Node {pc :: Int, children :: [Int]}
    deriving (Show, Eq)

data Edge = Edge {h :: Int, ic :: Int, u :: Int, v :: Int}
    deriving (Show, Eq)

instance Ord Edge where
    compare lhs rhs = comparing h rhs lhs `mappend` comparing ic lhs rhs

data Heap a = E | T Int a (Heap a) (Heap a)
    deriving (Show)
    
empty :: Heap a 
empty = E

null :: Heap a -> Bool 
null E = True
null _ = False

merge :: (Ord a) => Heap a -> Heap a -> Heap a
merge lh@(T _ lv la lb) rh@(T _ rv ra rb)
    | lv <= rv = makeT lv la $ merge lb rh
    | otherwise = makeT rv ra $ merge lh rb
    where
        makeT v a b
            | rank a >= rank b = T (rank b + 1) v a b
            | otherwise = T (rank a + 1) v b a
        rank (T r _ _ _) = r
        rank _ = 0
        
merge lh E = lh
merge _ rh = rh

push :: (Ord a) => a -> Heap a -> Heap a
push x = merge (T 1 x E E)

pop :: (Ord a) => Heap a -> Maybe (a, Heap a) 
pop (T _ x a b) = Just (x, merge a b)
pop _ = Nothing

fromList :: (Ord a) => [a] -> Heap a
fromList = br . fmap (\x -> T 1 x E E)
    where
        build (x : y : zs) = merge x y : build zs
        build xs = xs
        br [x] = x
        br xs = br $ build xs

readLine :: IO [Int]
readLine = unfoldr (\s -> second (maybe B.empty snd . B.uncons) <$> B.readInt s) <$> B.getLine

readContents :: Int -> IO [[Int]]
readContents = flip replicateM readLine